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

DOI10.1007/S10878-010-9315-9zbMATH Open1236.90135OpenAlexW1975834934MaRDI QIDQ411246FDOQ411246

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

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

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)

Cites Work

• Title not available (Why is that?)
• Unit disk graphs
• Approximation algorithms for NP-complete problems on planar graphs
• A linear-time approximation algorithm for the weighted vertex cover problem
• Approximation schemes for covering and packing problems in image processing and VLSI
• Title not available (Why is that?)
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• PTAS for connected vertex cover in 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
• An approximation scheme for some Steiner tree problems in the plane
• Node-weighted Steiner tree approximation in 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)