A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion

DOI10.1007/978-3-319-21398-9_37zbMath1347.68357OpenAlexW2264404578MaRDI QIDQ3196407

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

zbMATH Keywords

parameterized algorithmbranch and reducemeasure and conquerbounded degree-one deletionvertex cover \(P_3\)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ Unnamed Item ⋮ An \(O^\ast ( 2 . 61 9^k )\) algorithm for \textsc{4-path vertex cover} ⋮ On the vertex cover \(P_3\) problem parameterized by treewidth ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Faster parameterized algorithms for two vertex deletion problems ⋮ Kernelization and Parameterized Algorithms for 3-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 ⋮ A multi-start iterated greedy algorithm for the minimum weight vertex cover \(P_3\) problem ⋮ Kernels for packing and covering problems ⋮ Faster parameterized algorithm for cluster vertex deletion ⋮ A Parameterized Algorithm for Bounded-Degree Vertex Deletion ⋮ Parameterized algorithm for 3-path vertex cover ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• Exact exponential algorithms.
• 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
• Isolation concepts for efficiently enumerating dense subgraphs
• A general method to speed up fixed-parameter-tractable algorithms
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• Vertex Cover: Further Observations and Further Improvements
• Kernels for Packing and Covering Problems
• A measure & conquer approach for the analysis of exact algorithms
• Kernelization Algorithms for d-Hitting Set Problems

This page was built for publication: A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion