A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
From MaRDI portal
Publication:512868
DOI10.1007/s10878-015-9937-zzbMath1366.90204OpenAlexW2179466049MaRDI QIDQ512868
Zhao Zhang, Wenxue Du, Xiaoyan Zhang, Li-Min Wang
Publication date: 3 March 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-015-9937-z
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items
Unnamed Item ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
- A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
- Design and analysis of approximation algorithms
- A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
- A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
- Unit disk graph recognition is NP-hard
- Sphere packings. (Edited by John Talbot)
- 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
- A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
- Universality considerations in VLSI circuits
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- An approximation scheme for some Steiner tree problems in the plane
