{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T00:44:41Z","timestamp":1792111481410,"version":"4.4.0"},"publisher-location":"New York, NY","reference-count":15,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_608","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:20Z","timestamp":1461269000000},"page":"1143-1148","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Locality in Distributed Graph Algorithms"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"4","key":"608_CR12352","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 (1986) A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4): 567\u2013583","journal-title":"J. Algorithms"},{"key":"608_CR12353","series-title":"Synthesis lectures on distributed computing theory","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02009-4","volume-title":"Distributed graph coloring: fundamentals and recent developments","author":"L Barenboim","year":"2013","unstructured":"Barenboim L, Elkin M (2013) Distributed graph coloring: fundamentals and recent developments. Synthesis lectures on distributed computing theory. Morgan & Claypool Publishers"},{"issue":"1","key":"608_CR12354","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2014","unstructured":"Barenboim L, Elkin M, Kuhn F (2014) Distributed (Delta+1)-coloring in linear (in delta) time. SIAM J Comput 43(1):72\u201395","journal-title":"SIAM J Comput"},{"key":"608_CR12355","doi-asserted-by":"crossref","unstructured":"Barenboim L, Elkin M, Pettie S, Schneider J (2012) The locality of distributed symmetry breaking. In: Proceedings of the 53rd IEEE symposium on foundations of computer science (FOCS), New Brunswick, pp\u00a0321\u2013330","DOI":"10.1109\/FOCS.2012.60"},{"key":"608_CR12356","doi-asserted-by":"crossref","unstructured":"Cole R, Vishkin U (1986) Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In: Proceedings of the 18th ACM symposium on theory of computing (STOC), Berkeley, pp\u00a0206\u2013219","DOI":"10.1145\/12130.12151"},{"issue":"5","key":"608_CR12357","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud P, Korman A, Peleg D (2013) Towards a complexity theory for local distributed computing. J ACM 60(5):35","journal-title":"J ACM"},{"issue":"4","key":"608_CR12358","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman A, Kutten S, Peleg D (2010) Proof labeling schemes. Distrib Comput 22(4):215\u2013233","journal-title":"Distrib Comput"},{"issue":"1","key":"608_CR12359","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial N (1992) Locality in distributed graph algorithms. SIAM J Comput 21(1):193\u2013201","journal-title":"SIAM J Comput"},{"key":"608_CR12360","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby M (1986) A simple parallel algorithm for the maximal independent set problem. SIAM J Comput 15:1036\u20131053","journal-title":"SIAM J Comput"},{"issue":"3","key":"608_CR12361","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1137\/0404036","volume":"4","author":"M Naor","year":"1991","unstructured":"Naor M (1991) A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J Discret Math 4(3):409\u2013412","journal-title":"SIAM J Discret Math"},{"issue":"6","key":"608_CR12362","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor M, Stockmeyer L (1995) What can be computed locally? SIAM J Comput 24(6): 1259\u20131277","journal-title":"SIAM J Comput"},{"issue":"2","key":"608_CR12363","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A Panconesi","year":"1996","unstructured":"Panconesi A, Srinivasan A (1996) On the complexity of distributed network decomposition. J Algorithms 20(2):356\u2013374","journal-title":"J Algorithms"},{"key":"608_CR12364","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 (2000) Distributed computing: a locality-sensitive approach. SIAM, Philadelphia"},{"key":"608_CR12365","doi-asserted-by":"crossref","unstructured":"Schneider J, Wattenhofer R (2010) A new technique for distributed symmetry breaking. In: Proceedings of the 29th ACM symposium on principles of distributed computing (PODC), Zurich, pp\u00a0257\u2013266","DOI":"10.1145\/1835698.1835760"},{"issue":"2","key":"608_CR12366","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/2431211.2431223","volume":"45","author":"J Suomela","year":"2013","unstructured":"Suomela J (2013) Survey of local algorithms. ACM Comput Surv 45(2):24","journal-title":"ACM Comput Surv"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T23:56:46Z","timestamp":1792108606000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/chapter\/10.1007\/978-1-4939-2864-4_608"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_608","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}