The isomorphism problem for \(k\)-trees is complete for logspace

DOI10.1016/j.ic.2012.04.002zbMath1253.68161MaRDI QIDQ714733

Johannes Köbler, Bireswar Das, V. Arvind, Sebastian Kuhnert

Publication date: 11 October 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.04.002

zbMATH Keywords

graph isomorphism; \(k\)-trees; space complexity; graph canonization; logspace completeness

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

On the isomorphism problem for decision trees and decision lists

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph isomorphism is in the low hierarchy
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Group-theoretic algorithms and graph isomorphism
• A very hard log-space counting class
• Isomorphism for graphs of bounded distance width
• Counting quantifiers, successor relations, and logarithmic space
• Completeness results for graph isomorphism.
• The complexity of planarity testing
• Graph Isomorphism is in SPP
• Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$
• 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
• Undirected connectivity in log-space
• Testing Graph Isomorphism in Parallel by Playing a Game
• 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
• Algorithmic Aspects of Vertex Elimination on Graphs
• Bounded Tree-Width and LOGCFL
• On the Hardness of Graph Isomorphism
• The Space Complexity of k-Tree Isomorphism
• Fast parallel reordering and isomorphism testing of \(k\)-trees