{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T08:50:50Z","timestamp":1781686250891,"version":"3.54.5"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2010,3,10]],"date-time":"2010-03-10T00:00:00Z","timestamp":1268179200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s00446-010-0097-1","type":"journal-article","created":{"date-parts":[[2010,3,9]],"date-time":"2010-03-09T12:50:10Z","timestamp":1268139010000},"page":"349-361","source":"Crossref","is-referenced-by-count":53,"title":["An optimal maximal independent set\u00a0algorithm for bounded-independence graphs"],"prefix":"10.1007","volume":"22","author":[{"given":"Johannes","family":"Schneider","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,3,10]]},"reference":[{"issue":"4","key":"97_CR1","doi-asserted-by":"crossref","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 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"issue":"5","key":"97_CR2","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1109\/TPDS.2003.1195412","volume":"14","author":"K. Alzoubi","year":"2003","unstructured":"Alzoubi K., Li X., Wang Y., Wan P., Frieder O.: Geometric spanners for wireless ad hoc Networks. IEEE Trans. Parallel Distributed Syst. 14(5), 408\u2013421 (2003)","journal-title":"IEEE Trans. Parallel Distributed Syst."},{"key":"97_CR3","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1006\/jcss.1998.1580","volume":"57","author":"A. Andersson","year":"1998","unstructured":"Andersson A., Hagerup T., Nilsson S., Raman R.: Sorting in linear time. J. Comput. Syst. Sci. 57, 74\u201393 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"97_CR4","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"97_CR5","unstructured":"Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS) (1991)"},{"key":"97_CR6","doi-asserted-by":"crossref","unstructured":"Barenhoim, L., Elkin, M.: Sublogarithmic Distributed MIS Algorithm for Sparse Graphs using Nash-Williams Decomposition. In: Journal of Distributed Computing Special Issue of selected papers from PODC 2008 (2010)","DOI":"10.1145\/1400751.1400757"},{"key":"97_CR7","doi-asserted-by":"crossref","unstructured":"Bonorden, O., Degener, B., Kempkes, B., Pietrzyk, P.: Complexity and approximation of a geometric local robot assignment problem. In: ALGOSENSORS (2009)","DOI":"10.1007\/978-3-642-05434-1_25"},{"issue":"1","key":"97_CR8","doi-asserted-by":"crossref","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. Inf. Control 70(1), 32\u201354 (1986)","journal-title":"Inf. Control"},{"key":"97_CR9","doi-asserted-by":"crossref","unstructured":"Czygrinow, A., Hanckowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: DISC (2008)","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"97_CR10","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing (PODC) (2007)","DOI":"10.1145\/1281100.1281111"},{"issue":"4","key":"97_CR11","doi-asserted-by":"crossref","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 J. Discrete Math.(SIDMA) 1(4), 434\u2013446 (1988)","journal-title":"SIAM J. Discrete Math.(SIDMA)"},{"key":"97_CR12","doi-asserted-by":"crossref","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. Inf. Process. Lett. 22, 77\u201380 (1986)","journal-title":"Inf. Process. Lett."},{"key":"97_CR13","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Proceedings of the 19th International Symposium on Distributed Computing (DISC) (2005)","DOI":"10.1007\/11561927_21"},{"key":"97_CR14","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Local approximation schemes for ad hoc and sensor networks. In: Proceedings of the 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC) (2005)","DOI":"10.1145\/1080810.1080827"},{"key":"97_CR15","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pp. 60\u201368 (2005)","DOI":"10.1145\/1073814.1073826"},{"key":"97_CR16","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 300\u2013309 (2005)","DOI":"10.1145\/1011767.1011811"},{"key":"97_CR17","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wattenhofer, R.: Leveraging linial\u2019s locality limit. In: 22nd International Symposium on Distributed Computing (DISC) September (2008)","DOI":"10.1007\/978-3-540-87779-0_27"},{"issue":"1","key":"97_CR18","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"97_CR19","doi-asserted-by":"crossref","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 J. Comput. 15, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"97_CR20","doi-asserted-by":"crossref","unstructured":"Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), pp. 581\u2013592. ACM Press (1992)","DOI":"10.1145\/129712.129769"},{"key":"97_CR21","doi-asserted-by":"crossref","unstructured":"Pandit, S., Pemmaraju, S.: Finding facilities fast. In: Proceedings of the 10th International Conference on Distributed Computing and Networking (ICDCN) (2009)","DOI":"10.1007\/978-3-540-92295-7_5"},{"key":"97_CR22","doi-asserted-by":"crossref","unstructured":"Pirwani, I.A., Salavatipour, M.R.: A ptas for minimum clique partition in unit disk graphs. CoRR (2009)","DOI":"10.1007\/978-3-642-13731-0_19"},{"key":"97_CR23","doi-asserted-by":"crossref","unstructured":"Schneider J., Wattenhofer, R.: A log-star distributed maximal independent set\u00a0algorithm for growth-bounded graphs. In: 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August (2008)","DOI":"10.1145\/1400751.1400758"},{"key":"97_CR24","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: Coloring unstructured wireless multi-hop networks. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC) (2009)","DOI":"10.1145\/1582716.1582751"},{"key":"97_CR25","unstructured":"Sterling, A.: Self-assembling systems are distributed systems. CoRR (2009)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0097-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-010-0097-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0097-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:26:43Z","timestamp":1559136403000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-010-0097-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,10]]},"references-count":25,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["97"],"URL":"https:\/\/doi.org\/10.1007\/s00446-010-0097-1","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,10]]}}}