{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T19:21:31Z","timestamp":1769023291186,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540291633","type":"print"},{"value":"9783540320753","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561927_21","type":"book-chapter","created":{"date-parts":[[2005,10,10]],"date-time":"2005-10-10T10:14:47Z","timestamp":1128939287000},"page":"273-287","source":"Crossref","is-referenced-by-count":72,"title":["Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs"],"prefix":"10.1007","author":[{"given":"Fabian","family":"Kuhn","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Moscibroda","sequence":"additional","affiliation":[]},{"given":"Tim","family":"Nieberg","sequence":"additional","affiliation":[]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"21_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms\u00a07(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Alzoubi, K., Wan, P.-J., Frieder, O.: Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks. In: Proceedings of the 3rd ACM Int. Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), EPFL Lausanne, Switzerland, pp. 157\u2013164 (2002)","DOI":"10.1145\/513800.513820"},{"issue":"4","key":"21_CR3","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitziens dans R n . Bull. Soc. Math. France\u00a0111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proc. of the 30th Symp. on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/381448.381451","volume-title":"Proc. of the $\\mathit{5}^{th}$ International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M)","author":"L. Barri\u00e8re","year":"2001","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Narayanan, L.: Robust Position-Based Routing in Wireless Ad Hoc Networks with Unstable Transmission Ranges. In: Proc. of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), pp. 19\u201327. ACM Press, New York (2001)"},{"issue":"1-2","key":"21_CR6","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(1-2), 3\u201324 (1998)","journal-title":"Computational Geometry. Theory and Applications"},{"issue":"1","key":"21_CR7","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Information and Control\u00a070(1), 32\u201353 (1986)","journal-title":"Information and Control"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/978-3-540-30538-5_37","volume-title":"FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science","author":"R. Gandhi","year":"2004","unstructured":"Gandhi, R., Parthasarathy, S.: Distributed Algorithms for Coloring and Connected Domination in Wireless Ad Hoc Networks. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol.\u00a03328, pp. 447\u2013459. Springer, Heidelberg (2004)"},{"issue":"4","key":"21_CR9","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1137\/0401044","volume":"1","author":"A. Goldberg","year":"1988","unstructured":"Goldberg, A., Plotkin, S., Shannon, G.: Parallel Symmetry-Breaking in Sparse Graphs. SIAM Journal on Discrete Mathematics (SIDMA)\u00a01(4), 434\u2013446 (1988)","journal-title":"SIAM Journal on Discrete Mathematics (SIDMA)"},{"key":"21_CR10","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.: Bounded Geometries, Fractals, and Low-Distortion Embeddings. In: Proc. of 44th IEEE Symp. on Foundations of Computer Science, FOCS (2003)"},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A. Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A Fast and Simple Randomized Parallel Algorithm for Maximal Matching. Information Processing Letters\u00a022, 77\u201380 (1986)","journal-title":"Information Processing Letters"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Slivkins, A., Wexler, T.: Triangulation and Embedding using Small Sets of Beacons. In: Proc. of 45th IEEE Symp. on Foundations of Computer Science, FOCS (2004)","DOI":"10.1109\/FOCS.2004.70"},{"key":"21_CR13","unstructured":"Krauthgamer, R., Lee, J.: Navigating Nets: Simple Algorithms for Proximity Search. In: Proc. of 15th ACM-SIAM Symp. on Discrete Algorithms, SODA (2004)"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1022630.1022634","volume-title":"Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing (DIALM)","author":"F. Kuhn","year":"2004","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Unit Disk Graph Approximation. In: Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing (DIALM), pp. 17\u201323. ACM Press, New York (2004)"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What Cannot Be Computed Locally! In. In: Proc. of the 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The Locality of Bounded Growth. In: Proc. of the 24th ACM Symp. on Principles of Distributed Computing, PODC (2005)","DOI":"10.1145\/1073814.1073826"},{"key":"21_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1145\/941079.941089","volume-title":"Proceedings of 1st Joint Workshop on Foundations of Mobile Computing (DIALM-POMC)","author":"F. Kuhn","year":"2003","unstructured":"Kuhn, F., Wattenhofer, R., Zollinger, A.: Ad-Hoc Networks Beyond Unit Disk Graphs. In: Proceedings of 1st Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 69\u201378. ACM Press, New York (2003)"},{"issue":"1","key":"21_CR18","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":"21_CR19","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1017\/S0963548300000857","volume":"2","author":"N. Linial","year":"1993","unstructured":"Linial, N.: Local-Global Phenomena in Graphs. Combinatorics Probability and Computing\u00a02, 491\u2013503 (1993)","journal-title":"Combinatorics Probability and Computing"},{"key":"21_CR20","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing\u00a015, 1036\u20131053 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Maximal Independent Sets in Radio Networks. In: Proc. of the 23rd ACM Symp. on Principles of Distributed Computing, PODC (2005)","DOI":"10.1145\/1073814.1073842"},{"key":"21_CR22","first-page":"581","volume-title":"Proc. of the 24th annual ACM symposium on Theory of computing (STOC)","author":"A. Panconesi","year":"1992","unstructured":"Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: Proc. of the 24th annual ACM symposium on Theory of computing (STOC), pp. 581\u2013592. ACM Press, New York (1992)"},{"key":"21_CR23","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Plaxton, C.G., Rajaraman, R., Richa, A.W.: Accessing Nearby Copies of Replicated Objects in a Distributed Environment. In: Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 311\u2013320 (1997)","DOI":"10.1145\/258492.258523"},{"key":"21_CR25","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: Approximation schemes and compact representations for low dimensional metrics. In: Proc. of 36th ACM Symp. on Theory of Computing, STOC (2004)","DOI":"10.1145\/1007352.1007399"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561927_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:51:10Z","timestamp":1605624670000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561927_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291633","9783540320753"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11561927_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}