{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:14Z","timestamp":1759638074174,"version":"3.34.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78773-0_14","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T08:38:35Z","timestamp":1207211915000},"page":"158-169","source":"Crossref","is-referenced-by-count":11,"title":["Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes"],"prefix":"10.1007","author":[{"given":"J.","family":"Czyzowicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Dobrev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Fevens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Gonz\u00e1lez-Aguilar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Kranakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Opatrny","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected-dominating-set construction for routing in mobile ad hoc networks. In: MOBIHOC 2002, pp. 157\u2013164 (2002)","DOI":"10.1145\/513800.513820"},{"key":"14_CR2","unstructured":"Aspnes, J., Bush, C., Dolev, S., Fatouroum, P., Georgiou, C., Shvartsman, A., Spirakis, P., Wattenhofer, R.: Eight open problems in distributed computing. Bulletin of the European Association for Theoretical Computer Science\u00a090(109) (October 2006) Columns: Distributed Computing."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Peleg, D.: Sparse partitions (extended abstract). In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 503\u2013513 (1990)","DOI":"10.1109\/FSCS.1990.89571"},{"key":"14_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H. Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Computational Geometry: Theory and Applications\u00a09, 3\u201324 (1998)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/11682462_29","volume-title":"LATIN 2006: Theoretical Informatics","author":"E. Ch\u00e1vez","year":"2006","unstructured":"Ch\u00e1vez, E., Dobrev, S., Kranakis, E., Opatrny, J., Stacho, L., Urrutia, J.: Local construction of planar spanners in unit disk graphs with irregular transmission ranges. In: Correa, J.R., Hevia, A., Kiwi, M.A. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 286\u2013297. Springer, Heidelberg (2006)"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X. Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Du, D.-Z.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks\u00a042, 202\u2013208 (2003)","journal-title":"Networks"},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics\u00a086, 165\u2013177 (1990)","journal-title":"Discrete Mathematics"},{"key":"14_CR8","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.jda.2006.07.001","volume":"5","author":"A. Dessmark","year":"2007","unstructured":"Dessmark, A., Pelc, A.: Broadcasting in geometric radio networks. Journal of Discrete Algorithms\u00a05, 187\u2013201 (2007)","journal-title":"Journal of Discrete Algorithms"},{"key":"14_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00446-003-0091-y","volume":"16","author":"F. Fich","year":"2003","unstructured":"Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distributed Computing\u00a016, 121\u2013163 (2003)","journal-title":"Distributed Computing"},{"issue":"3","key":"14_CR10","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1145\/1167935.1167941","volume":"2","author":"S. Funke","year":"2006","unstructured":"Funke, S., Kesselman, A., Meyer, U., Segal, M.: A simple improved distributed algorithm for minimum cds in unit disk graphs. ACM Transactions on Sensor Networks\u00a02(3), 444\u2013453 (2006)","journal-title":"ACM Transactions on Sensor Networks"},{"issue":"2","key":"14_CR11","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms\u00a026(2), 238\u2013274 (1998)","journal-title":"Journal of Algorithms"},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"R.W. Irving","year":"1991","unstructured":"Irving, R.W.: On approximating the minimum independent dominating set. Information Processing Letters\u00a037, 197\u2013200 (1991)","journal-title":"Information Processing Letters"},{"issue":"1","key":"14_CR13","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s00454-003-2925-6","volume":"30","author":"J. Gao","year":"2001","unstructured":"Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Discrete Mobile Centers. Discrete & Computational Geometry\u00a030(1), 45\u201363 (2001)","journal-title":"Discrete & Computational Geometry"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00446-002-0078-0","volume":"14","author":"L. Jia","year":"2002","unstructured":"Jia, L., Rajaraman, R., Suel, R.: An efficient distributed algorithm for constructing small dominating sets. Distributed Computing\u00a014, 193\u2013205 (2002)","journal-title":"Distributed Computing"},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. Johnson","year":"1974","unstructured":"Johnson, D.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences\u00a09, 256\u2013278 (1974)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"14_CR16","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00446-004-0112-5","volume":"17","author":"F. Kuhn","year":"2005","unstructured":"Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. Distributed Computing\u00a017(4), 303\u2013310 (2005)","journal-title":"Distributed Computing"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: 23th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Unit disk graph approximation. In: DialM: Proceedings of the Discrete Algorithms and Methods for Mobile Computing & Communications; later DIALM-POMC Joint Workshop on Foundations of Mobile Computing, pp. 17\u201323 (2004)","DOI":"10.1145\/1022630.1022634"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Local approximation schemes for ad hoc and sensor networks. In: DialM: Proceedings of the Discrete Algorithms and Methods for Mobile Computing & Communications; later DIALM-POMC Joint Workshop on Foundations of Mobile Computing, pp. 97\u2013103 (2005)","DOI":"10.1145\/1080810.1080827"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: 24th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 60\u201368 (2005)","DOI":"10.1145\/1073814.1073826"},{"key":"14_CR21","doi-asserted-by":"publisher","first-page":"980","DOI":"10.1145\/1109557.1109666","volume-title":"SODA","author":"F. Kuhn","year":"2006","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: SODA, pp. 980\u2013989. ACM Press, New York (2006)"},{"issue":"1","key":"14_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: Proc. 17th Annual ACM Symposium on Theory of Computing (STOCS), May 1985, pp. 1\u201310 (1985)","DOI":"10.1145\/22145.22146"},{"key":"14_CR24","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. Journal of the ACM\u00a041, 960\u2013981 (1994)","journal-title":"Journal of the ACM"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Geometry based heuristics for unit disk graphs. ArXiv Mathematics e-prints (1994)","DOI":"10.1002\/net.3230250205"},{"key":"14_CR26","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M. Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. on Computing\u00a024, 1259\u20131277 (1995)","journal-title":"SIAM J. on Computing"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Nieberg, T., Hurink, J.: A PTAS for the minimum dominating set problem in unit disk graphs. In: Approximation and Online Algorithms, pp. 296\u2013306 (2006)","DOI":"10.1007\/11671411_23"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"14_CR29","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/941079.941088","volume-title":"Proc. of the 2003 joint workshop on Foundations of mobile computing (DIALM-POMC 2003)","author":"Y. Wang","year":"2003","unstructured":"Wang, Y., Li, X.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. In: Proc. of the 2003 joint workshop on Foundations of mobile computing (DIALM-POMC 2003), pp. 59\u201368. ACM Press, New York (2003)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T11:54:36Z","timestamp":1738151676000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540787723","9783540787730"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_14","relation":{},"subject":[]}}