Fixed-parameter algorithms for Vertex Cover \(P_3\)
From MaRDI portal
Publication:1751145
DOI10.1016/j.disopt.2015.11.003zbMath1387.05248OpenAlexW2218434618MaRDI QIDQ1751145
Li-Hsuan Chen, Peter Rossmanith, Maw-Shang Chang, Ling-Ju Hung, Ping-Chen Su
Publication date: 24 May 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2015.11.003
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (22)
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} ⋮ A \(5k\)-vertex kernel for 3-path vertex cover ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ On the \(d\)-claw vertex deletion problem ⋮ 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 ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ Kernels for packing and covering problems ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network ⋮ Faster parameterized algorithm for cluster vertex deletion ⋮ On the \(d\)-claw vertex deletion problem ⋮ Algorithm for online 3-path vertex cover ⋮ Parameterized algorithm for 3-path vertex cover ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing} ⋮ An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
Cites Work
- 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
- On bounded-degree vertex deletion parameterized by treewidth
- Isolation concepts for efficiently enumerating dense subgraphs
- An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
- On two techniques of combining branching and treewidth
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Minimum \(k\)-path vertex cover
- On the vertex \(k\)-path cover
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Kernels for Packing and Covering Problems
This page was built for publication: Fixed-parameter algorithms for Vertex Cover \(P_3\)
