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