Graph isomorphism parameterized by elimination distance to bounded degree

DOI10.1007/S00453-015-0045-3MaRDI QIDQ309797zbMATH OpenOpenAlexWikidataFDO

Authors Jannis Bulian, Anuj Dawar

Publication date 7 September 2016

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-015-0045-3

zbMATH Keywords

graph theorycomplexity theorygraph isomorphismparameterized complexitytree-depthbounded degreecanonizationfixed-parameter tractable

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• On tractable parameterizations of graph isomorphism
• On the parallel parameterized complexity of the graph isomorphism problem
• Isomorphism for graphs of bounded distance width

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A generalization of Nemhauser and Trotter's local optimization theorem
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Graph Layout Problems Parameterized by Vertex Cover
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Isomorphism for graphs of bounded distance width
• Isomorphism for graphs of bounded feedback vertex set number
• Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• On tractable parameterizations of graph isomorphism
• Parameterized and Exact Computation
• Parametrized complexity theory.
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• The isomorphism problem for classes of graphs closed under contraction

Cited in

(22)

• Backdoor DNFs
• Elimination Distance to Bounded Degree on Planar Graphs
• SAT backdoors: depth beats size
• Elimination Distances, Blocking Sets, and Kernels for Vertex Cover
• Reduction Techniques for Graph Isomorphism in the Context of Width Parameters
• CSP beyond tractable constraint languages
• A graph searching game for block treedepth and a cubic kernel by vertex cover
• Elimination distance to bounded degree on planar graphs preprint
• On the Parameterized Complexity of Clique Elimination Distance
• Faster parameterized algorithms for modification problems to minor-closed classes
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• FPT algorithms to compute the elimination distance to bipartite graphs and more
• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• First-order Logic with Connectivity Operators
• Distance from triviality 2.0: hybrid parameterizations
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
• On the parallel parameterized complexity of the graph isomorphism problem
• On tractable parameterizations of graph isomorphism
• Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
• Block elimination distance
• Block elimination distance
• Graph editing problems with extended regularity constraints

This page was built for publication: Graph isomorphism parameterized by elimination distance to bounded degree

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