[evonetwork] Nauty
- From: Russell Standish <r.standish@xxxxxxxxxxx>
- To: evonetwork@xxxxxxxxxxxxx
- Date: Tue, 24 May 2005 11:07:08 +1000
Hi guys,
In an effort to resurrect this list, I'd thought I'd post this
interesting snippet:
Th algorithm I described for canonical labelling of graphs at the
network workshop in March actually fails for graphs of order 6 (I only
checked it by hand for graphs of order 3 & 4) :(. I don't know why,
exactly, but the nice thing is that this discovery forced me to do a
Google search, and I came across software called Nauty written by
Brendan McKay (whom you may know at ANU) that actually solves the
problem in a highly efficient way. It can easily handle graphs of order
several 1000 on my laptop.
So I'm now working on a version of my library that calls Nauty to
determine the \omega of my paper. It turns out that Nauty computes
n!/\omega, which it calls the "groupsize". You can enter an arbitrary
graph into Brendan's command line program dreadnaut, and compare.
I'm looking at extending this idea by weighting each graph
representation by a complexity value computed using gzip (as a proxy
for computing the full Kolmogov complexity) to see if this alters the
basic results (that fully (un)connected graphs have maximal complexity
in the set of all graphs of a given order.
Cheers
--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.
----------------------------------------------------------------------------
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics 0425 253119 (")
UNSW SYDNEY 2052 R.Standish@xxxxxxxxxxx
Australia http://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------
-- Attached file included as plaintext by Ecartis --
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)
iD8DBQFCkn48u0uihy7TX/oRAmg6AJ96MOQEUYlIRpYEyBZbNvxpHvO2LACfTMiQ
wEQuRnJcdHoa6mngcE5xtYE=
=e06W
-----END PGP SIGNATURE-----
Other related posts:
