Graph isomorphism parameterized by elimination distance to bounded degree

DOI10.1007/S00453-015-0045-3zbMATH Open1350.68132OpenAlexW1777447092WikidataQ59475369 ScholiaQ59475369MaRDI QIDQ309797FDOQ309797

Authors Jannis Bulian, Anuj Dawar

Publication date 7 September 2016

Published in Algorithmica (Search for Journal in Brave)

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)

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

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)