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

DOI10.1007/S10878-010-9315-9MaRDI QIDQ411246zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

Cites work

• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A linear-time approximation algorithm for the weighted vertex cover problem
• An approximation scheme for some Steiner tree problems in the plane
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Node-weighted Steiner tree approximation in unit disk graphs
• On approximability of the independent/connected edge dominating set problems
• PTAS for connected vertex cover in unit disk graphs
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks
• Unit disk graphs

Cited in

(7)

• PTAS for connected vertex cover in unit disk graphs
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• A PTAS for the Weighted Unit Disk Cover Problem
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• The price of connectivity for cycle transversals

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

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