On tractable parameterizations of graph isomorphism

DOI10.1007/978-3-642-33293-7_21MaRDI QIDQ4899255zbMATH OpenOpenAlexWikidataFDO

Authors Adam Bouland, Anuj Dawar, Eryk Kopczyński

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-33293-7_21

Mathematics Subject Classification ID

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

Recommendations

• Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
• 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
• Graph isomorphism parameterized by elimination distance to bounded degree
• Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree

Cited in

(25)

• Isomorphism for graphs of bounded distance width
• On the parallel parameterized complexity of the graph isomorphism problem
• Parameterized complexity of small weight automorphisms and isomorphisms
• Isomorphism testing for \(T\)-graphs in FPT
• Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics
• Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs
• A note on the connected game coloring number
• Colored hypergraph isomorphism is fixed parameter tractable
• Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Graph isomorphism parameterized by elimination distance to bounded degree
• Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
• Isomorphism for graphs of bounded feedback vertex set number
• Isomorphism for graphs of bounded connected-path-distance-width
• Recent advances on the graph isomorphism problem
• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• scientific article; zbMATH DE number 7559375 (Why is no real title available?)
• Benchmark Graphs for Practical Graph Isomorphism
• Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
• Logspace and FPT algorithms for graph isomorphism for subclasses of bounded tree-width graphs
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• On the Parameterized Complexity of Clique Elimination Distance
• Graph isomorphism in quasipolynomial time parameterized by treewidth
• An FPT algorithm for elimination distance to bounded degree graphs
• On the generic complexity of the searching graph isomorphism problem

This page was built for publication: On tractable parameterizations of graph isomorphism

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