The Isomorphism Problem for k-Trees Is Complete for Logspace

DOI10.1007/978-3-642-03816-7_46MaRDI QIDQ3182953zbMATH OpenOpenAlexFDO

Authors 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

\(k\)-treesgraph canonizationgraph isomorphismlogspace completenessspace complexity

Mathematics Subject Classification ID

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

Recommendations

• The isomorphism problem for \(k\)-trees is complete for logspace
• The Space Complexity of k-Tree Isomorphism
• Canonizing Graphs of Bounded Tree Width in Logspace
• Canonizing graphs of bounded tree width in logspace
• A Logspace Algorithm for Partial 2-Tree Canonization

Cites work

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

Cited in

(10)

• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Graphs of bounded treewidth can be canonized in AC^1
• Log-space algorithms for paths and matchings in \(k\)-trees
• Log-space algorithms for paths and matchings in k-trees
• scientific article; zbMATH DE number 1088188 (Why is no real title available?)
• The Space Complexity of k-Tree Isomorphism
• Graph isomorphism restricted by lists
• The isomorphism problem for \(k\)-trees is complete for logspace
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Isomorphism testing of k-trees is in NC, for fixed k

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3182953)