The Space Complexity of k-Tree Isomorphism

DOI10.1007/978-3-540-77120-3_71zbMath1193.68124OpenAlexW1591409247MaRDI QIDQ5387816

V. Arvind, Bireswar Das, Johannes Köbler

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

The Isomorphism Problem for k-Trees Is Complete for Logspace ⋮ Log-space algorithms for paths and matchings in \(k\)-trees ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ A computational approach to construct a multivariate complete graph invariant ⋮ The isomorphism problem for \(k\)-trees is complete for logspace

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

This page was built for publication: The Space Complexity of k-Tree Isomorphism