The isomorphism problem for k-trees is complete for logspace

DOI10.1016/J.IC.2012.04.002MaRDI QIDQ714733zbMATH OpenOpenAlexFDO

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

\(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)

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

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

Cited in

(7)

• Count-free Weisfeiler-Leman and group isomorphism
• Isomorphism testing of k-trees is in NC, for fixed k
• On the isomorphism problem for decision trees and decision lists
• Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
• Log-space algorithms for paths and matchings in \(k\)-trees
• The Space Complexity of k-Tree Isomorphism
• The Isomorphism Problem for k-Trees Is Complete for Logspace

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)