The Isomorphism Problem for k-Trees Is Complete for Logspace

DOI10.1007/978-3-642-03816-7_46zbMath1250.68120OpenAlexW2155065925MaRDI QIDQ3182953

Sebastian Kuhnert, Johannes Köbler

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_46

zbMATH Keywords

graph isomorphism\(k\)-treesspace complexitygraph canonizationlogspace completeness

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Log-space algorithms for paths and matchings in \(k\)-trees ⋮ Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$ ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs ⋮ Graph isomorphism restricted by lists

Cites Work

• Graph isomorphism is in the low hierarchy
• Group-theoretic algorithms and graph isomorphism
• A very hard log-space counting class
• Counting quantifiers, successor relations, and logarithmic space
• Completeness results for graph isomorphism.
• The complexity of planarity testing
• Graph Isomorphism is in SPP
• A Logspace Algorithm for Partial 2-Tree Canonization
• Undirected ST-connectivity in log-space
• A taxonomy of problems with fast parallel algorithms
• Isomorphism Testing in Hookup Classes
• Parallel Tree Contraction Part 2: Further Applications
• Structure and importance of logspace-MOD class
• On the Hardness of Graph Isomorphism
• The Space Complexity of k-Tree Isomorphism
• Fast parallel reordering and isomorphism testing of \(k\)-trees
• Unnamed Item
• Unnamed Item

This page was built for publication: The Isomorphism Problem for k-Trees Is Complete for Logspace