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

treesouterplanar graphplanar graphinterval graphgraph automorphismlabeled forestautomorphism partitionlinear time automorphism algorithms

Mathematics Subject Classification ID

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)

Cited in

(28)

• Quantum algorithm for lexicographically minimal string rotation
• Plane graphs with parity constraints
• Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
• Minimal representatives of endofunctions
• Determining sets, resolving sets, and the exchange property
• The QAP-polytope and the graph isomorphism problem
• Practical graph isomorphism. II.
• A fast average case algorithm for lyndon decomposition
• A selected tour of the theory of identification matrices
• Lexicographically least circular substrings
• Isomorphism testing for \(T\)-graphs in FPT
• Graph isomorphism and identification matrices: Sequential algorithms
• Minimal obstructions for partial representations of interval graphs
• Fast detection and display of symmetry in outerplanar graphs
• Counting graceful labelings of trees: a theoretical and empirical study
• Farey Series and Maximal Outerplanar Graphs
• Minimal obstructions for partial representations of interval graphs
• Relationships between symmetry-based graph measures
• Cleaning interval graphs
• Plane Graphs with Parity Constraints
• Canonical representations of partial 2-and 3-trees
• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• The list distinguishing number equals the distinguishing number for interval graphs
• Relations and bounds for the zeros of graph polynomials using vertex orbits
• 3-connected reduction for regular graph covers
• Measuring tree balance using symmetry nodes -- a new balance index and its extremal properties
• On uniform circuit complexity
• Canonical representations of partial 2- and 3-trees

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)