A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs

DOI10.1016/j.tcs.2015.01.005zbMath1312.68234OpenAlexW2053240544MaRDI QIDQ2512658

Xiaoyan Zhang, Zhao Zhang, Hajo J. Broersma, Li-Min Wang

Publication date: 30 January 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.01.005

zbMATH Keywords

vertex coverPTASgrid graphunit disk graphconnected cover\(c\)-local problem\(P_3\) coverminimum weight cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (7)

Unnamed Item ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ 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 ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network ⋮ An efficient local search framework for the minimum weighted vertex cover problem

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 primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Node-weighted Steiner tree approximation in unit disk graphs
• PTAS for connected vertex cover in unit disk graphs
• On approximability of the independent/connected edge dominating set problems
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• An improved LP-based approximation for steiner tree
• Universality considerations in VLSI circuits
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• An approximation scheme for some Steiner tree problems in the plane

This page was built for publication: A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs