[Nauty] Vertex orbits in Nauty
Lluís Alemany Puig
lluis.alemany.puig at upc.edu
Tue Sep 19 18:28:56 AEST 2023
Hello,
Well, that is very interesting. A colleague of mine actually proposed
that vertex orbits in a tree should be computable in linear time in the
number of vertices of the tree. So these references are very helpful.
Thank you!
Lluís
On 17/09/2023 02:09, Kevin Ryde wrote:
> Lluís Alemany Puig <lluis.alemany.puig at upc.edu> writes:
>> some references
> If it may help,
>
> Colbourn and Booth, "Linear Time Automorphism Algorithms for Trees,
> Interval Graphs, and Planar Graphs", 1981
>
> who in turn refer to (but I haven't seen)
>
> Fontet, "Linear Algorithms for Testing Isomorphism of Planar Graphs", 1976
>
> The broad idea is work upwards from childless vertices to the
> root, assigning "id" numbers to each vertex according to the
> structure of the subtree below there. Vertices must be sorted
> by id at each phase to ensure same ids for same structure, but
> that's a bucket sort so still linear time.
>
> Using Nauty, I'd found sparsenauty() a bit faster on trees
> (they're sparse :), and that for a rooted tree it helps to use
> an undirected graph with root vertex distinguished (initial lab
> and ptn), rather than a directed graph.
More information about the Nauty
mailing list