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

DOI10.1016/j.ic.2012.04.002zbMath1253.68161OpenAlexW2052024655MaRDI 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\)-treesspace complexitygraph canonizationlogspace completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (1)

On the isomorphism problem for decision trees and decision lists

Cites Work

• 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
• Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
• Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$
• Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
• 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

This page was built for publication: The isomorphism problem for \(k\)-trees is complete for logspace