Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- 1 January 2006
- book chapter
- conference paper
- Published by Springer Science and Business Media LLC in Lecture Notes in Computer Science
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- Selecting Forwarding Neighbors in Wireless Ad Hoc NetworksMobile Networks and Applications, 2004
- A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networksNetworks, 2003
- Message-optimal connected dominating sets in mobile ad hoc networksPublished by Association for Computing Machinery (ACM) ,2002
- 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
- Almost optimal set covers in finite VC-dimensionDiscrete & Computational Geometry, 1995
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- Unit disk graphsDiscrete Mathematics, 1990
- Approximation schemes for covering and packing problems in image processing and VLSIJournal of the ACM, 1985
- Planar Formulae and Their UsesSIAM Journal on Computing, 1982