Approximating minimum independent dominating sets in wireless networks

Breu, 1998, Unit disk graph recognition is NP-hard, Computational Geometry. Theory and Applications, 9, 3, 10.1016/S0925-7721(97)00014-X Chan, 2003, Polynomial-time approximation schemes for packing and piercing fat objects, Journal of Algorithms, 46, 178, 10.1016/S0196-6774(02)00294-8 Cheng, 2003, A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks, Networks, 42, 202, 10.1002/net.10097 Clark, 1990, Unit disks graphs, Discrete Mathematics, 86, 165, 10.1016/0012-365X(90)90358-O P. Crescenzi, V. Kann (Eds.), A compendium of NP optimization problems, http://www.nada.kth.se/~viggo/problemlist/ Erlebach, 2005, Polynomial-time approximation schemes for geometric intersection graphs, SIAM Journal of Computing, 34, 1302, 10.1137/S0097539702402676 EYES Halldorson, 1993, Approximating the minimum maximal independence number, Information Processing Letters, 46, 169, 10.1016/0020-0190(93)90022-2 Hunt, 1998, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, 26, 238, 10.1006/jagm.1997.0903 J. Kratochvil, Intersection graphs of noncrossing arc-connected sets in the plane, in: Proc. Symp. on Graph Drawing (GD'96), 1997, pp. 257–270 F. Kuhn, R. Wattenhofer, A. Zollinger, Ad-hoc networks beyond unit disk graphs, in: Proc. 1st ACM DIALM-POMC Joint Workshop on Foundations of Mobile Computing, 2003 Li, 2003, Algorithmic, geometric and graphs issues in wireless networks, Wireless Communications and Mobile Computing, 3, 119, 10.1002/wcm.107 Marathe, 1995, Simple heuristics for unit disk graphs, Networks, 25, 59, 10.1002/net.3230250205 T. Nieberg, J.L. Hurink, Wireless communication graphs, in: Proc. Intelligent Sensors, Sensor Networks and Information Processing Conference, 2004, pp. 367–372 Nieberg, 2005, A PTAS for the minimum dominating set problem in unit disk graphs, vol. 3879, 296 Nieberg, 2004, A robust PTAS for maximum independent sets in unit disk graphs, vol. 3353, 214 Raghavan, 2003, Robust algorithms for restricted domains, Journal of Algorithms, 48, 160, 10.1016/S0196-6774(03)00048-8