On bounded-degree vertex deletion parameterized by treewidth
From MaRDI portal
Publication:765338
DOI10.1016/j.dam.2011.08.013zbMath1236.05064OpenAlexW2043193111MaRDI QIDQ765338
Rolf Niedermeier, Nadja Betzler, Johannes Uhlmann, Robert Bredereck
Publication date: 19 March 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.08.013
parameterized complexityvector dominating setstructural parameterization\(k\)-dependent settree-likenessco-\(k\)-plexes
Related Items (31)
Approximating Bounded Degree Deletion via Matroid Matching ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ On the parameterized complexity of maximum degree contraction problem ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ Studies in Computational Aspects of Voting ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ Subexponential Fixed-Parameter Algorithms for Partial Vector Domination ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ Hitting forbidden subgraphs in graphs of bounded treewidth ⋮ Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Parameterized orientable deletion ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Approximating power node-deletion problems ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ Unnamed Item ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Latency-bounded target set selection in social networks ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Fixed-parameter algorithms for Vertex Cover \(P_3\) ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ On the Parameterized Complexity of Maximum Degree Contraction Problem. ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Kernels for packing and covering problems ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- A generalization of Nemhauser and Trotter's local optimization theorem
- Isolation concepts for efficiently enumerating dense subgraphs
- Parameterized complexity of candidate control in elections and related digraph problems
- A partial k-arboretum of graphs with bounded treewidth
- Reduction algorithms for graphs of small treewidth
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- Parametrized complexity theory.
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- On Making a Distinguished Vertex Minimum Degree by Vertex Deletion
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Capacitated Domination and Covering: A Parameterized Perspective
- A Linear Kernel for Co-Path/Cycle Packing
- Graph Layout Problems Parameterized by Vertex Cover
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- Kernelization: New Upper and Lower Bound Techniques
- Graph minors. II. Algorithmic aspects of tree-width
- A graph‐theoretic generalization of the clique concept
- Parameterized Algorithms for Generalized Domination
This page was built for publication: On bounded-degree vertex deletion parameterized by treewidth
