PTAS for minimum k-path vertex cover in ball graph
DOI10.1016/J.IPL.2016.11.003zbMATH Open1401.68365OpenAlexW2552909035MaRDI QIDQ503602FDOQ503602
Zhao Zhang, Yuqing Zhu, Hongmei Nie, Xiaoting Li, Yishuo Shi
Publication date: 13 January 2017
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2016.11.003
Recommendations
- A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
- Minimum \(k\)-path vertex cover
- PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
- A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
- A faster FPT algorithm for 3-path vertex cover
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- The node-deletion problem for hereditary properties is NP-complete
- A unified approximation algorithm for node-deletion problems
- On the \(k\)-path vertex cover of some graph products
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- Minimum \(k\)-path vertex cover
- PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
- Narrow sieves for parameterized paths and packings
- The vertex cover \(P_3\) problem in cubic graphs
- On the vertex \(k\)-path cover
- Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
- Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
- A 2-approximation algorithm for the vertex coverP4problem in cubic graphs
- Node-Deletion NP-Complete Problems
- On the weighted \(k\)-path vertex cover problem
- A fixed-parameter algorithm for the vertex cover \(P_3\) problem
- Improved results on geometric hitting set problems
- 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
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Minimum vertex cover in ball graphs through local search
- Approximation algorithms for maximum independent set of pseudo-disks
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- The \(k\)-path vertex cover of rooted product graphs
- A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
- A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
- Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
- A faster FPT algorithm for 3-path vertex cover
Cited In (9)
- Vertex cover at distance on \(H\)-free graphs
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- Approximation algorithm for minimum connected 3-path vertex cover
- Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
- A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
- Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
- PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
- A PTAS for the cardinality constrained covering with unit balls
- Title not available (Why is that?)
This page was built for publication: PTAS for minimum \(k\)-path vertex cover in ball graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q503602)
