Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
From MaRDI portal
Publication:3904620
DOI10.1137/0210015zbMath0456.05024OpenAlexW2023154896MaRDI QIDQ3904620
Kellogg S. Booth, Charles J. Colbourn
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210015
treesplanar graphinterval graphouterplanar graphgraph automorphismlabeled forestautomorphism partitionlinear time automorphism algorithms
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)
Related Items
Farey Series and Maximal Outerplanar Graphs ⋮ The QAP-polytope and the graph isomorphism problem ⋮ Canonical representations of partial 2-and 3-trees ⋮ Plane Graphs with Parity Constraints ⋮ Isomorphism testing for \(T\)-graphs in FPT ⋮ 3-connected reduction for regular graph covers ⋮ Minimal Obstructions for Partial Representations of Interval Graphs ⋮ Relations and bounds for the zeros of graph polynomials using vertex orbits ⋮ Counting graceful labelings of trees: a theoretical and empirical study ⋮ Cleaning interval graphs ⋮ Lexicographically least circular substrings ⋮ Relationships between symmetry-based graph measures ⋮ Quantum algorithm for lexicographically minimal string rotation ⋮ On uniform circuit complexity ⋮ Practical graph isomorphism. II. ⋮ A fast average case algorithm for lyndon decomposition ⋮ Plane graphs with parity constraints ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ Minimal obstructions for partial representations of interval graphs ⋮ The list distinguishing number equals the distinguishing number for interval graphs ⋮ Canonical representations of partial 2- and 3-trees ⋮ Fast detection and display of symmetry in outerplanar graphs ⋮ Determining sets, resolving sets, and the exchange property ⋮ Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs ⋮ Measuring tree balance using symmetry nodes -- a new balance index and its extremal properties ⋮ A selected tour of the theory of identification matrices ⋮ On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
