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

DOI10.1007/978-3-540-85097-7_24zbMath1168.68448OpenAlexW1890004479MaRDI QIDQ5505664

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

unit disk graphconnected vertex cover

Mathematics Subject Classification ID

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

Related Items

Vertex and edge covers with clustering properties: Complexity and algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating the tree and tour covers of a graph
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Depth-first search and the vertex cover problem
• Optimization, approximation, and complexity classes
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• An approximation scheme for some Steiner tree problems in the plane
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Reducibility among Combinatorial Problems
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs