Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$
From MaRDI portal
Publication:3007628
DOI10.1007/978-3-642-20712-9_16zbMath1332.68092OpenAlexW2232592548MaRDI QIDQ3007628
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
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
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