Graph isomorphism parameterized by elimination distance to bounded degree

DOI10.1007/s00453-015-0045-3zbMath1350.68132OpenAlexW1777447092WikidataQ59475369 ScholiaQ59475369MaRDI QIDQ309797

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 theoryparameterized complexitygraph isomorphismtree-depthbounded degreecanonizationfixed-parameter tractable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (14)

Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel ⋮ A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ First-order Logic with Connectivity Operators ⋮ SAT backdoors: depth beats size ⋮ CSP beyond tractable constraint languages ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ Graph editing problems with extended regularity constraints ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ Block elimination distance ⋮ Block elimination distance ⋮ Elimination Distance to Bounded Degree on Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalization of Nemhauser and Trotter's local optimization theorem
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• The isomorphism problem for classes of graphs closed under contraction
• Isomorphism for graphs of bounded distance width
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks
• Parametrized complexity theory.
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Isomorphism for Graphs of Bounded Feedback Vertex Set Number
• Graph Layout Problems Parameterized by Vertex Cover
• On Tractable Parameterizations of Graph Isomorphism
• Parameterized and Exact Computation
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs

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