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
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
graph theorycomplexity theorygraph isomorphismparameterized complexitytree-depthbounded degreecanonizationfixed-parameter tractable
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)
Cites Work
- Parametrized complexity theory.
- Title not available (Why is that?)
- Title not available (Why is that?)
- A generalization of Nemhauser and Trotter's local optimization theorem
- Title not available (Why is that?)
- Parameterized and Exact Computation
- 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
- 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
- Structure theorem and isomorphism test for graphs with excluded topological subgraphs
Cited In (21)
- Backdoor DNFs
- A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs
- Elimination Distance to Bounded Degree on Planar Graphs
- SAT backdoors: depth beats size
- Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
- 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
- First-order Logic with Connectivity Operators
- Distance from triviality 2.0: hybrid parameterizations
- 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)
