[Nauty] Isomorphism with coloured multigraphs

[Sterten at aol.com]

In einer eMail vom 29.04.2004 16:01:31 Westeuropäische Sommerzeit schreibt  
pdarga at umich.edu:

Symmetry  detection, and particularly nauty's implementation, are very
sensitive to  the number of vertices in the graph.  If you can find a
construction  of your problem that minimizes the number of vertices, yet
still encodes  all of the information about the problem (particularly,
which makes  vertices maximally distinguishable), then nauty will be
much  happier.

Coloring vertices is the best way to make such a thing  happen.
While it might not be the most general theoretical approach, it  is
in fact how nauty finds the automorphism group of a graph in  the
first place.  Providing an initial vertex coloring helps nauty out  a
great deal since it doesn't need to "discover" this initial  coloring
on its own by wading through a sea of extraneous  vertices.

Paul

I don't think so.
If this were the case, then there might be room for improving  Nauty....
Nauty should detect such situations somehow and handle them
appropriately.
Guenter.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20040430/90af4c5a/attachment.html