Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph

DOI10.1007/978-3-540-85097-7_24MaRDI QIDQ5505664zbMATH OpenOpenAlexFDO

Authors Zhao Zhang, Xiaofeng Gao, Weili Wu

Publication date 27 January 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85097-7_24

zbMATH Keywords

connected vertex coverunit disk graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs

Cites work

• A 2-approximation NC algorithm for connected vertex cover and tree cover
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• An approximation scheme for some Steiner tree problems in the plane
• Approximating the tree and tour covers of a graph
• Approximation algorithms for NP-hard problems.
• Depth-first search and the vertex cover problem
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• Optimization, approximation, and complexity classes
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Reducibility among combinatorial problems
• Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(9)

• Vertex and edge covers with clustering properties: Complexity and algorithms
• PTAS for connected vertex cover in unit disk graphs
• The connected disk covering problem
• An efficient heuristic algorithm for solving connected vertex cover problem
• Minimum vertex cover in ball graphs through local search
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• Polynomial time approximation schemes for minimum disk cover problems

This page was built for publication: Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph

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