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

DOI10.1137/0210015MaRDI QIDQ3904620zbMATH OpenOpenAlexFDO

Authors Charles J. Colbourn, Kellogg S. Booth

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

zbMATH Keywords

automorphism partitiongraph automorphisminterval graphlabeled forestlinear time automorphism algorithmsouterplanar graphplanar graphtrees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(36)

• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• Lexicographically least circular substrings
• On uniform circuit complexity
• Canonical representations of partial 2- and 3-trees
• Fast detection and display of symmetry in outerplanar graphs
• A selected tour of the theory of identification matrices
• The QAP-polytope and the graph isomorphism problem
• 3-connected reduction for regular graph covers
• Cleaning interval graphs
• Graph isomorphism and identification matrices: Sequential algorithms
• Measuring tree balance using symmetry nodes -- a new balance index and its extremal properties
• Isomorphism testing for \(T\)-graphs in FPT
• Relations and bounds for the zeros of graph polynomials using vertex orbits
• Practical graph isomorphism. II.
• Plane graphs with parity constraints
• Minimal obstructions for partial representations of interval graphs
• Plane Graphs with Parity Constraints
• Farey Series and Maximal Outerplanar Graphs
• A fast average case algorithm for lyndon decomposition
• The list distinguishing number equals the distinguishing number for interval graphs
• Canonical representations of partial 2-and 3-trees
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Relationships between symmetry-based graph measures
• Quantum algorithm for lexicographically minimal string rotation
• Minimal representatives of endofunctions
• Minimal obstructions for partial representations of interval graphs
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
• Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism
• A note on quantum divide and conquer for minimal string rotation
• Automorphisms and isomorphisms of maps in linear time
• Testing network correlation efficiently via counting trees
• Faster algorithms for the alignment of sparse correlated Erdős-Rényi random graphs
• Automorphisms and isomorphisms of maps in linear time
• An algorithm for uniform generation of unlabeled (Pólya) trees
• Counting graceful labelings of trees: a theoretical and empirical study
• Determining sets, resolving sets, and the exchange property

This page was built for publication: Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3904620)