[Nauty] A decreasing runtime with an increasing number of edges of an isomorphism test

Kukluk, Jacek P kukluk at uta.edu
Sun Feb 13 05:14:02 EST 2005


We studied an isomorphism test of planar graphs. Our paper was accepted
in JGAA and we are working on some revisions.  We used Nauty as a
reference in comparing performance. We observed that Nauty's runtime
decreases with increasing number of edges. We would like to understand
why. 
 
More specifically, in one of our experiments, we generate one thousand
planar graphs with number of vertices |V|=80. We repeated two times this
experiment with isomorphic and nonisomorphic graphs. As we increase
number of edges from |V|-1 to 3|V|-6 we observe decreasing running time.
We did this experiment with other number of vertices with the same
result. How to explain this phenomenon which appears to be
counter-intuitive?
 
Jacek Kukluk
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.anu.edu.au/mailman/private/nauty/attachments/20050213/0a4bd65b/attachment.html 


More information about the Nauty mailing list