Restricted space algorithms for isomorphism on bounded treewidth graphs

DOI10.1016/j.ic.2012.05.003zbMath1251.05167OpenAlexW2129003155MaRDI QIDQ714737

Fabian Wagner, Bireswar Das, Jacobo Toran

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.05.003

zbMATH Keywords

complexityalgorithmstreewidthgraph isomorphism problemlogCFL

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) 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
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• A partial k-arboretum of graphs with bounded treewidth
• Isomorphism for graphs of bounded distance width
• Completeness results for graph isomorphism.
• Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Undirected connectivity in log-space
• Testing Graph Isomorphism in Parallel by Playing a Game
• Bounded Tree-Width and LOGCFL
• Computing LOGCFL certificates

This page was built for publication: Restricted space algorithms for isomorphism on bounded treewidth graphs