On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
From MaRDI portal
Publication:3304132
DOI10.4230/LIPIcs.STACS.2018.33zbMath1487.68177OpenAlexW2793933268MaRDI QIDQ3304132
Sebastian Ordyniak, Fabian Klute, Robert Ganian
Publication date: 5 August 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.STACS.2018.33
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (11)
On the parameterized complexity of maximum degree contraction problem ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Unnamed Item ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ Unnamed Item ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Kernelization using structural parameters on sparse graph classes
- Fundamentals of parameterized complexity
- Sparsity. Graphs, structures, and algorithms
- Combinatorial algorithms for the maximum \(k\)-plex problem
- The structure of graphs not admitting a fixed immersion
- A generalization of Nemhauser and Trotter's local optimization theorem
- Backdoors into heterogeneous classes of SAT and CSP
- On bounded-degree vertex deletion parameterized by treewidth
- Isolation concepts for efficiently enumerating dense subgraphs
- Meta-kernelization with structural parameters
- Treewidth. Computations and approximations
- The multidimensional 0-1 knapsack problem: an overview.
- Which problems have strongly exponential complexity?
- An FPT 2-approximation for tree-cut decomposition
- Reduction algorithms for graphs of small treewidth
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- A complete parameterized complexity analysis of bounded planning
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Algorithmic Applications of Tree-Cut Width
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- Integer Programming with a Fixed Number of Variables
- Solving Problems on Graphs of High Rank-Width
- A Linear Kernel for Co-Path/Cycle Packing
- A graph‐theoretic generalization of the clique concept
- Immersions in Highly Edge Connected Graphs
- Meta-kernelization using Well-structured Modulators
- Parameterized Algorithms
This page was built for publication: On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
