Restricted space algorithms for isomorphism on bounded treewidth graphs

DOI10.1016/J.IC.2012.05.003MaRDI QIDQ714737zbMATHOpenAlexFDO

Authors Bireswar Das, Fabian Wagner, Jacobo Torán

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

algorithmscomplexitytreewidthgraph isomorphism problemlogCFL

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Canonizing Graphs of Bounded Tree Width in Logspace
• Canonizing graphs of bounded tree width in logspace
• Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
• Isomorphism for graphs of bounded distance width

Cites work

• scientific article; zbMATH DE number 3571498 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Bounded Tree-Width and LOGCFL
• Completeness results for graph isomorphism.
• Computing LOGCFL certificates
• Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
• Isomorphism for graphs of bounded distance width
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Testing Graph Isomorphism in Parallel by Playing a Game
• The Isomorphism Problem for k-Trees Is Complete for Logspace
• Undirected connectivity in log-space

Cited in

(10)

• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
• On the isomorphism problem for decision trees and decision lists
• Bounded treewidth and space-efficient linear algebra
• Graphs of bounded treewidth can be canonized in AC\(^1\)
• Canonizing graphs of bounded tree width in logspace
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
• The Space Complexity of k-Tree Isomorphism
• Isomorphism for graphs of bounded connected-path-distance-width

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714737)