A 5+ϵ-approximation algorithm for minimum weighted dominating set in unit disk graph
Open Access
- 1 March 2009
- journal article
- Published by Elsevier BV in Theoretical Computer Science
- Vol. 410 (8-10), 756-765
- https://doi.org/10.1016/j.tcs.2008.11.015
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk GraphsLecture Notes in Computer Science, 2006
- Message-optimal connected dominating sets in mobile ad hoc networksPublished by Association for Computing Machinery (ACM) ,2002
- On calculating connected dominating set for efficient routing in ad hoc wireless networksPublished by Association for Computing Machinery (ACM) ,1999
- 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
- 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