Restricted space algorithms for isomorphism on bounded treewidth graphs

DOI10.4230/LIPICS.STACS.2010.2457zbMATH Open1230.68088OpenAlexW2571406257MaRDI QIDQ3113751FDOQ3113751

Jacobo Torán, Bireswar Das, Fabian Wagner

Publication date: 23 January 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_0785.html

Recommendations

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

zbMATH Keywords

treewidthgraph isomorphism problemcomplexity of algorithmsLogCFL

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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) Distance in graphs (05C12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (5)

• The isomorphism problem for \(k\)-trees is complete for logspace
• Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
• Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf 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 Q3113751)