Isomorphism for graphs of bounded connected-path-distance-width

DOI10.1007/978-3-642-35261-4_48MaRDI QIDQ4909562zbMATH OpenOpenAlexFDO

Authors Yota Otachi

Publication date 21 March 2013

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-35261-4_48

zbMATH Keywords

treewidthfixed-parameter tractabilitygraph isomorphismconnected-path-distance-width

Mathematics Subject Classification ID

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

Recommendations

• Isomorphism for graphs of bounded distance width
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Restricted space algorithms for isomorphism on bounded treewidth graphs
• Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
• On tractable parameterizations of graph isomorphism

Cited in

(5)

• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• On weak isomorphism of rooted vertex-colored graphs
• Isomorphisms and traversability of directed path graphs
• Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
• On the parallel parameterized complexity of the graph isomorphism problem

This page was built for publication: Isomorphism for graphs of bounded connected-path-distance-width

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