Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs

By Charles J. Colbourn, Kellogg S. Booth. 1981

Subfields: Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

1. Oleg Verbitsky
2. Oleg Pikhurko
3. B. Douglas

Citations in the corpus

• The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, background): “Efficient GI algorithms do exist for several restricted classes of graphs, such as trees [13], planar graphs [20] and graphs with certain bounded parameters, including valence [22], eigenvalue multiplicity [5] and genus [26].”
• Practical graph isomorphism, II (2013, neutral): “Only for a very few important graph classes, such as trees (Aho et al., 1974) and planar graphs (Colbourn and Booth, 1981) are there practical approaches which are sure to outperform general methods such as described in this paper.”
• Logical complexity of graphs: a survey (2010, background): “, [16]), and its logical interpretation is due to Immerman and Lander [47].”