A-approximation algorithm for minimum weighted dominating set in unit disk graph
Authors:
- Decheng DaiDDDecheng Dai
- Changyuan YuCYChangyuan Yu
- 1 March 2009
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 410 (8-10) , 756-765
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs2006
- Message-optimal connected dominating sets in mobile ad hoc networks2002
- On calculating connected dominating set for efficient routing in ad hoc wireless networks1999
- Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating SetsInformation and Computation, 1999
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric GraphsJournal of Algorithms, 1998
- A threshold of ln n for approximating set cover (preliminary version)1996
- Simple heuristics for unit disk graphsNetworks, 1995
- Unit disk graphsDiscrete Mathematics, 1990
- On approximation problems related to the independent set and vertex cover problemsDiscrete Applied Mathematics, 1984
- Planar Formulae and Their UsesSIAM Journal on Computing, 1982