PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs

DOI10.1007/s10878-010-9315-9zbMath1236.90135OpenAlexW1975834934MaRDI QIDQ411246

Lidan Fan, Zhao Zhang, Wei Wang

Publication date: 4 April 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9315-9

zbMATH Keywords

unit disk graph\(c\)-localminimum weighted connected vertex coverpolynomial time approximation scheme

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (3)

A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks ⋮ A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs ⋮ The price of connectivity for cycle transversals

Cites Work

• Unnamed Item
• Unnamed Item
• Node-weighted Steiner tree approximation in unit disk graphs
• PTAS for connected vertex cover in unit disk graphs
• Unit disk graphs
• On approximability of the independent/connected edge dominating set problems
• Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks
• Approximation schemes for covering and packing problems in image processing and VLSI
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation algorithms for NP-complete problems on planar graphs
• An approximation scheme for some Steiner tree problems in the plane
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs

This page was built for publication: PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs