A measure and conquer approach for the parameterized bounded degree-one vertex deletion
DOI10.1007/978-3-319-21398-9_37zbMATH Open1347.68357OpenAlexW2264404578MaRDI QIDQ3196407FDOQ3196407
Authors: Bang Ye Wu 
Publication date: 29 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-21398-9_37
Recommendations
- A parameterized algorithm for bounded-degree vertex deletion
- On structural parameterizations of the bounded-degree vertex deletion problem
- On structural parameterizations of the bounded-degree vertex deletion problem
- Bounded-degree techniques accelerate some parameterized graph algorithms
- On bounded-degree vertex deletion parameterized by treewidth
measure and conquerparameterized algorithmbranch and reducebounded degree-one deletionvertex cover \(P_3\)
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Fundamentals of parameterized complexity
- A measure \& conquer approach for the analysis of exact algorithms
- Exact exponential algorithms.
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- A generalization of Nemhauser and Trotter's local optimization theorem
- Improved upper bounds for vertex cover
- On bounded-degree vertex deletion parameterized by treewidth
- Kernels for Packing and Covering Problems
- Title not available (Why is that?)
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Vertex cover: Further observations and further improvements
- Isolation concepts for efficiently enumerating dense subgraphs
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- A general method to speed up fixed-parameter-tractable algorithms
- Kernelization Algorithms for d-Hitting Set Problems
Cited In (20)
- An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
- On the vertex cover \(P_3\) problem parameterized by treewidth
- A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem
- Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- The weighted \(k\)-path vertex cover problem on series-parallel graphs
- Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
- Faster parameterized algorithm for cluster vertex deletion
- Faster parameterized algorithms for two vertex deletion problems
- An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover
- PTAS for minimum \(k\)-path vertex cover in ball graph
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- Kernels for packing and covering problems
- A faster FPT algorithm for 3-path vertex cover
- A \(5k\)-vertex kernel for 3-path vertex cover
- Parameterized algorithm for 3-path vertex cover
- A parameterized algorithm for bounded-degree vertex deletion
- Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
- Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs
This page was built for publication: A measure and conquer approach for the parameterized bounded degree-one vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196407)
