{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:36:31Z","timestamp":1782970591471,"version":"3.54.5"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2009,9,3]],"date-time":"2009-09-03T00:00:00Z","timestamp":1251936000000},"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-009-0088-2","type":"journal-article","created":{"date-parts":[[2009,9,2]],"date-time":"2009-09-02T12:13:36Z","timestamp":1251893616000},"page":"363-379","source":"Crossref","is-referenced-by-count":95,"title":["Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition"],"prefix":"10.1007","volume":"22","author":[{"given":"Leonid","family":"Barenboim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Elkin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,9,3]]},"reference":[{"issue":"4","key":"88_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":"1\u20133","key":"88_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0166-218X(97)00007-3","volume":"78","author":"S.R. Arikati","year":"1997","unstructured":"Arikati S.R., Maheshwari A., Zaroliagis C.: Efficient computation of implicit representations of sparse graphs. Discrete Appl. Math. 78(1\u20133), 1\u201316 (1997)","journal-title":"Discrete Appl. Math."},{"key":"88_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: Proceedings of the 30th Symposium on Foundations of Computer Science, pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"88_CR4","volume-title":"Extremal Graph Theory","author":"B. Bollobas","year":"1978","unstructured":"Bollobas B.: Extremal Graph Theory. Academic Press, New York (1978)"},{"issue":"1","key":"88_CR5","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\u201353 (1986)","journal-title":"Inf. Control"},{"key":"88_CR6","unstructured":"Deo, N., Litow, B.: A structural approach to graph compression. In: Proceedings of the MFCS Workshop on Communications, pp. 91\u2013100 (1998)"},{"issue":"4","key":"88_CR7","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s00454-007-1318-7","volume":"37","author":"V. Dujmovic","year":"2007","unstructured":"Dujmovic V., Wood D.R.: Graph treewidth and geometric thickness parameters. Discrete Comput. Geom. 37(4), 641\u2013670 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"88_CR8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF02772959","volume":"51","author":"P. Erd\u0151s","year":"1985","unstructured":"Erd\u0151s P., Frankl P., F\u00fcredi Z.: Families of finite sets in which no set is covered by the union of r others. Isr. J. Math. 51, 79\u201389 (1985)","journal-title":"Isr. J. Math."},{"key":"88_CR9","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, pp. 53\u201360 (2007)","DOI":"10.1145\/1281100.1281111"},{"key":"88_CR10","doi-asserted-by":"crossref","unstructured":"Goldberg, A., Plotkin, S.: Efficient parallel algorithms for (\u0394 +\u00a01)- coloring and maximal independent set problem. In: Proceedings of the 19th ACM Symposium on Theory of Computing, pp. 315\u2013324 (1987)","DOI":"10.1145\/28395.28429"},{"issue":"4","key":"88_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. 1(4), 434\u2013446 (1988)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"88_CR12","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/0890-5401(90)90004-2","volume":"88","author":"A. Itai","year":"1990","unstructured":"Itai A., Rodeh M.: Symmetry breaking in distributed networks. Inf. Comput. 88(1), 60\u201387 (1990)","journal-title":"Inf. Comput."},{"key":"88_CR13","doi-asserted-by":"crossref","unstructured":"Kothapalli, K., Scheideler, C., Onus, M., Schindelhauer, C.: Distributed coloring in $${\\tilde O(\\sqrt{\\log n})}$$ bit rounds. In: Proceedings of the 20th International Parallel and Distributed Processing Symposium, p. 24 (2006)","DOI":"10.1109\/IPDPS.2006.1639281"},{"key":"88_CR14","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, pp. 273\u2013287 (2005)","DOI":"10.1007\/11561927_21"},{"key":"88_CR15","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, pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"88_CR16","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: Proceedings of the 24rd ACM Symposium on Principles of Distributed Computing, pp. 60\u201368 (2005)","DOI":"10.1145\/1073814.1073826"},{"key":"88_CR17","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, pp. 7\u201315 (2006)","DOI":"10.1145\/1146381.1146387"},{"issue":"1","key":"88_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":"88_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":"88_CR20","first-page":"145","volume-title":"Surveys in Combinatorics.","author":"B. Mohar","year":"2001","unstructured":"Mohar B.: Graph minors and graphs on surfaces. In: Hirschfeld, J.W.P.(eds) Surveys in Combinatorics., pp. 145\u2013163. London Mathematical Society Lecture Note Series 288. Cambridge University Press, Cambridge (2001)"},{"key":"88_CR21","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"39","author":"C. Nash-Williams","year":"1964","unstructured":"Nash-Williams C.: Decompositions of finite graphs into forests. J. Lond. Math. 39, 12 (1964)","journal-title":"J. Lond. Math."},{"issue":"2","key":"88_CR22","first-page":"581","volume":"20","author":"A. Panconesi","year":"1995","unstructured":"Panconesi A., Srinivasan A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581\u2013592 (1995)","journal-title":"J. Algorithms"},{"key":"88_CR23","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":"88_CR24","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set\u00a0algorithm for growth bounded graphs. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, pp. 35\u201344 (2008)","DOI":"10.1145\/1400751.1400758"},{"issue":"3","key":"88_CR25","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s004460050033","volume":"10","author":"G. Singh","year":"1997","unstructured":"Singh G.: Efficient leader election using sense of direction. Distrib. Comput. 10(3), 159\u2013165 (1997)","journal-title":"Distrib. Comput."},{"key":"88_CR26","doi-asserted-by":"crossref","unstructured":"Szegedy, M., Vishwanathan, S.: Locality based graph coloring. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 201\u2013207 (1993)","DOI":"10.1145\/167088.167156"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-009-0088-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-009-0088-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-009-0088-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T23:26:30Z","timestamp":1739316390000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-009-0088-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,3]]},"references-count":26,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["88"],"URL":"https:\/\/doi.org\/10.1007\/s00446-009-0088-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,3]]}}}