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

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) 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

(22)

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

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)