A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
From MaRDI portal
Publication:724732
DOI10.1007/s10878-018-0283-9zbMath1402.90139OpenAlexW2794918889WikidataQ130058266 ScholiaQ130058266MaRDI QIDQ724732
Lina Chen, Zhao Zhang, Xiao-hui Huang
Publication date: 26 July 2018
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-018-0283-9
Related Items (5)
The k‐path vertex cover: General bounds and chordal graphs ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover
Cites Work
- Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
- PTAS for minimum \(k\)-path vertex cover in ball graph
- A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- An inequality in the geometry of numbers
- A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
- A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
- 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
- A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
- A NEW PROOF FOR ZASSENHAUS–GROEMER–OLER INEQUALITY
- A PTAS FOR MINIMUM d-HOP UNDERWATER SINK PLACEMENT PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
- Approximation schemes for covering and packing problems in image processing and VLSI
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
This page was built for publication: A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network