Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$

DOI10.1007/978-3-642-20712-9_16zbMath1332.68092OpenAlexW2232592548MaRDI QIDQ3007628

Fabian Wagner

Publication date: 17 June 2011

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-20712-9_16

zbMATH Keywords

graph isomorphismbounded treewidthcanonization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The isomorphism problem for \(k\)-trees is complete for logspace

Cites Work

• Unnamed Item
• A partial k-arboretum of graphs with bounded treewidth
• Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
• Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
• 3-connected Planar Graph Isomorphism is in Log-space
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• A Logspace Algorithm for Partial 2-Tree Canonization
• From Invariants to Canonization in Parallel
• Testing Graph Isomorphism in Parallel by Playing a Game
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Bounded Tree-Width and LOGCFL
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Logical Approaches to Computational Barriers