The isomorphism problem for k-trees is complete for logspace

DOI10.1016/J.IC.2012.04.002zbMATH Open1253.68161OpenAlexW2052024655MaRDI QIDQ714733FDOQ714733

Johannes Köbler, Bireswar Das, Vikraman 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

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

zbMATH Keywords

\(k\)-treesgraph isomorphismspace complexitygraph canonizationlogspace completeness

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Undirected connectivity in log-space
• A taxonomy of problems with fast parallel algorithms
• On the Hardness of Graph Isomorphism
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Group-theoretic algorithms and graph isomorphism
• Algorithmic Aspects of Vertex Elimination on Graphs
• Isomorphism for graphs of bounded distance width
• Structure and importance of logspace-MOD class
• Graph Isomorphism is in SPP
• Graph isomorphism is in the low hierarchy
• Parallel Tree Contraction Part 2: Further Applications
• Title not available (Why is that?)
• Completeness results for graph isomorphism.
• A very hard log-space counting class
• Counting quantifiers, successor relations, and logarithmic space
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• Bounded Tree-Width and LOGCFL
• The Space Complexity of k-Tree Isomorphism
• Fast parallel reordering and isomorphism testing of \(k\)-trees
• Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
• Title not available (Why is that?)
• The complexity of planarity testing
• Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$
• Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
• A Logspace Algorithm for Partial 2-Tree Canonization
• From Invariants to Canonization in Parallel
• Testing Graph Isomorphism in Parallel by Playing a Game
• Isomorphism Testing in Hookup Classes
• Title not available (Why is that?)

Cited In (4)

• On the isomorphism problem for decision trees and decision lists
• Isomorphism testing of k-trees is in NC, for fixed k
• Count-free Weisfeiler-Leman and group isomorphism
• The Space Complexity of k-Tree Isomorphism

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 Q714733)