The Space Complexity of k-Tree Isomorphism
From MaRDI portal
Publication:5387816
DOI10.1007/978-3-540-77120-3_71zbMath1193.68124MaRDI QIDQ5387816
V. Arvind, Johannes Köbler, Bireswar Das
Publication date: 27 May 2008
Published in: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_71
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Log-space algorithms for paths and matchings in \(k\)-trees, The isomorphism problem for \(k\)-trees is complete for logspace, The Isomorphism Problem for k-Trees Is Complete for Logspace, A Logspace Algorithm for Partial 2-Tree Canonization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Isomorphism testing of k-trees is in NC, for fixed k
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- RUSPACE\((\log n)\subseteq \text{DSPACE}(\log^2n/\log \log n)\)
- Treewidth. Computations and approximations
- Completeness results for graph isomorphism.
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
- Testing Graph Isomorphism in Parallel by Playing a Game
- NC algorithms for recognizing chordal graphs and k trees
- Isomorphism Testing in Hookup Classes
- Bounded Tree-Width and LOGCFL
- Relationships among $PL$, $\#L$, and the determinant
- A combinatorial and logical approach to linear-time computability (extended abstract)
- Fast parallel reordering and isomorphism testing of \(k\)-trees
