On structural parameterizations of the bounded-degree vertex deletion problem
From MaRDI portal
Publication:2223699
DOI10.1007/s00453-020-00758-8zbMath1487.68178OpenAlexW3065763739MaRDI QIDQ2223699
Robert Ganian, Fabian Klute, Sebastian Ordyniak
Publication date: 1 February 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-020-00758-8
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 (10)
On structural parameterizations of the offensive alliance problem ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Hedonic diversity games: a complexity picture with more than two colors ⋮ Parameterized intractability of defensive alliance problem ⋮ Extended MSO model checking via small vertex integrity ⋮ Group activity selection with few agent types ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing} ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Cites Work
- Unnamed Item
- 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
- On making a distinguished vertex of minimum degree by vertex deletion
- 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
- Parameterized complexity of candidate control in elections and related digraph problems
- An application of simultaneous diophantine approximation in combinatorial optimization
- 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
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- The power of cut-based parameters for computing edge disjoint paths
- Backdoors to planning
- 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
- On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
- Solving Problems on Graphs of High Rank-Width
- A Linear Kernel for Co-Path/Cycle Packing
- Graph Layout Problems Parameterized by Vertex Cover
- Minkowski's Convex Body Theorem and Integer Programming
- A graph‐theoretic generalization of the clique concept
- Kernelization Lower Bounds by Cross-Composition
- Immersions in Highly Edge Connected Graphs
- SAT-Encodings for Treecut Width and Treedepth
- Meta-kernelization using Well-structured Modulators
- Parameterized Algorithms
- On a Problem of Sidon in Additive Number Theory, and on some Related Problems
This page was built for publication: On structural parameterizations of the bounded-degree vertex deletion problem
