A PTAS for minimum weighted connected vertex cover P₃ problem in 3-dimensional wireless sensor networks

DOI10.1007/S10878-015-9937-ZMaRDI QIDQ512868zbMATH OpenOpenAlexFDO

Authors Wenxue Du, Zhao Zhang, Xiaoyan Zhang, Limin 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

zbMATH Keywords

connected vertex cover \(P_3\)PTASsmooth weightsunit ball graphweak \(c\)-local

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks

Cites work

• A factor 2 approximation algorithm for the vertex cover P₃ problem
• 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
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs
• An approximation scheme for some Steiner tree problems in the plane
• Design and analysis of approximation algorithms
• Graph theory
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• Minimum \(k\)-path vertex cover
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Sphere packings. (Edited by John Talbot)
• The Rectilinear Steiner Tree Problem is NP-Complete
• Unit disk graph recognition is NP-hard
• Universality considerations in VLSI circuits

Cited in

(7)

• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Approximation algorithms for minimum weight connected 3-path vertex cover
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• The weighted k-path vertex cover problem on series-parallel graphs
• A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network

This page was built for publication: A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q512868)