On bounded-degree vertex deletion parameterized by treewidth
From MaRDI portal
Publication:765338
DOI10.1016/J.DAM.2011.08.013zbMATH Open1236.05064OpenAlexW2043193111MaRDI QIDQ765338FDOQ765338
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
Recommendations
- On structural parameterizations of the bounded-degree vertex deletion problem
- On structural parameterizations of the bounded-degree vertex deletion problem
- A parameterized algorithm for bounded-degree vertex deletion
- Losing Treewidth by Separating Subsets
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
parameterized complexityvector dominating setstructural parameterization\(k\)-dependent settree-likenessco-\(k\)-plexes
Cites Work
- A partial k-arboretum of graphs with bounded treewidth
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A Linear Kernel for Co-Path/Cycle Packing
- Title not available (Why is that?)
- A generalization of Nemhauser and Trotter's local optimization theorem
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- Graph minors. II. Algorithmic aspects of tree-width
- Title not available (Why is that?)
- A graph‐theoretic generalization of the clique concept
- Parameterized Algorithms for Generalized Domination
- Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
- Graph Layout Problems Parameterized by Vertex Cover
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Isolation concepts for efficiently enumerating dense subgraphs
- Kernelization: New Upper and Lower Bound Techniques
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- Capacitated Domination and Covering: A Parameterized Perspective
- Parameterized complexity of candidate control in elections and related digraph problems
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Reduction algorithms for graphs of small treewidth
- On Making a Distinguished Vertex Minimum Degree by Vertex Deletion
- Title not available (Why is that?)
Cited In (34)
- Studies in Computational Aspects of Voting
- Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- Grundy Distinguishes Treewidth from Pathwidth
- Approximating Partially Bounded Degree Deletion on Directed Graphs
- Maximum weight t-sparse set problem on vector-weighted graphs
- Trimming weighted graphs of bounded treewidth
- A Parameterized Algorithm for Bounded-Degree Vertex Deletion
- Title not available (Why is that?)
- Approximating power node-deletion problems
- Approximating power node-deletion problems
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- Subexponential fixed-parameter algorithms for partial vector domination
- (Total) vector domination for graphs with bounded branchwidth
- Title not available (Why is that?)
- Complexity and kernels for bipartition into degree-bounded induced graphs
- A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
- Parameterized orientable deletion
- Hitting forbidden subgraphs in graphs of bounded treewidth
- On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem
- On the parameterized complexity of maximum degree contraction problem
- On a generalization of Nemhauser and Trotter's local optimization theorem
- On the Parameterized Complexity of Maximum Degree Contraction Problem.
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- Subexponential Fixed-Parameter Algorithms for Partial Vector Domination
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- Tree-edges deletion problems with bounded diameter obstruction sets
- Kernels for packing and covering problems
- On structural parameterizations of the bounded-degree vertex deletion problem
- Latency-bounded target set selection in social networks
- Title not available (Why is that?)
- Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
- Approximating Bounded Degree Deletion via Matroid Matching
- On making a distinguished vertex of minimum degree by vertex deletion
This page was built for publication: On bounded-degree vertex deletion parameterized by treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765338)
