Restricted space algorithms for isomorphism on bounded treewidth graphs

DOI10.1016/J.IC.2012.05.003zbMATH Open1251.05167OpenAlexW2129003155MaRDI QIDQ714737FDOQ714737

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

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

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)

Cites Work

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

Cited In (5)

• On the isomorphism problem for decision trees and decision lists
• Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
• Graphs of bounded treewidth can be canonized in AC\(^1\)
• The Space Complexity of k-Tree Isomorphism
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

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)