Fixed-parameter tractable distances to sparse graph classes

DOI10.1007/s00453-016-0235-7zbMath1379.68160arXiv1502.05910OpenAlexW2099200602WikidataQ59613680 ScholiaQ59613680MaRDI QIDQ2408199

Jannis Bulian, Anuj Dawar

Publication date: 10 October 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.05910

zbMATH Keywords

distancegraph theoryparameterized complexitysparse graphsexcluded minorfixed-parameter tractablenowhere densedeletion distanceminor-closedelimination distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ First-order Logic with Connectivity Operators ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Graph extensions, edit number and regular graphs ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ 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 ⋮ Discrete density comonads and graph parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Editing graphs to satisfy degree constraints: a parameterized approach
• Sparsity. Graphs, structures, and algorithms
• Graph editing problems with extended regularity constraints
• Graph minors. XX: Wagner's conjecture
• Parameterized coloring problems on chordal graphs
• On the fixed-parameter tractability of parameterized model-checking problems
• Homomorphism preservation on quasi-wide classes
• Fixed-parameter algorithms for cluster vertex deletion
• Parameterized complexity of finding regular induced subgraphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Editing to a graph of given degrees
• Parametrized complexity theory.
• Strongly regular graphs, partial geometries and partially balanced designs
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Kernelization Using Structural Parameters on Sparse Graph Classes
• Editing to a Connected Graph of Given Degrees
• Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree
• Deciding first-order properties of locally tree-decomposable structures
• Finite Model Theory on Tame Classes of Structures
• Deciding First-Order Properties of Nowhere Dense Graphs
• Parameterized and Exact Computation

This page was built for publication: Fixed-parameter tractable distances to sparse graph classes