Polynomial time approximation schemes for minimum disk cover problems

DOI10.1007/s10878-009-9216-yzbMath1206.90150OpenAlexW2048364862MaRDI QIDQ613664

Chen Liao, Shiyan Hu

Publication date: 21 December 2010

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

Full work available at URL: https://doi.org/10.1007/s10878-009-9216-y

zbMATH Keywords

wireless networkminimum weight disk cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (2)

Online unit covering in Euclidean space ⋮ Experiments with unit disk cover algorithms for covering massive pointsets

Cites Work

• Unnamed Item
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• A better constant-factor approximation for weighted dominating set in unit disk graph
• Unit disk graphs
• Almost optimal set covers in finite VC-dimension
• An optimal algorithm for the minimum disc cover problem
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximation schemes for wireless networks
• The NP-completeness column: An ongoing guide

This page was built for publication: Polynomial time approximation schemes for minimum disk cover problems