{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:27Z","timestamp":1750694787025,"version":"3.40.3"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031099922"},{"type":"electronic","value":"9783031099939"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-09993-9_1","type":"book-chapter","created":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T20:12:42Z","timestamp":1656101562000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Local Mending"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5293-8365","authenticated-orcid":false,"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[]},{"given":"Juho","family":"Hirvonen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5614-8563","authenticated-orcid":false,"given":"Darya","family":"Melnyk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6600-6443","authenticated-orcid":false,"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6432-6646","authenticated-orcid":false,"given":"Joel","family":"Rybicki","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6117-8089","authenticated-orcid":false,"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,25]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","unstructured":"Aboulker, P., Bonamy, M., Bousquet, N., Esperet, L.: Distributed coloring in sparse graphs with fewer colors. Electr. J. Comb. 26(4) (2019). https:\/\/doi.org\/10.37236\/8395","DOI":"10.37236\/8395"},{"key":"1_CR2","doi-asserted-by":"publisher","unstructured":"Afek, Y., Dolev, S.: Local stabilizer. In: PODC (1997). https:\/\/doi.org\/10.1145\/259380.259505","DOI":"10.1145\/259380.259505"},{"issue":"2","key":"1_CR3","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1006\/jpdc.1996.0159","volume":"39","author":"B Awerbuch","year":"1996","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Fast distributed network decompositions and covers. J. Parallel Distrib. Comput. 39(2), 105\u2013114 (1996). https:\/\/doi.org\/10.1006\/jpdc.1996.0159","journal-title":"J. Parallel Distrib. Comput."},{"key":"1_CR4","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: FOCS (1991). https:\/\/doi.org\/10.1109\/SFCS.1991.185378","DOI":"10.1109\/SFCS.1991.185378"},{"key":"1_CR5","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Sipser, M.: Dynamic networks are as fast as static networks. In: FOCS (1988). https:\/\/doi.org\/10.1109\/SFCS.1988.21938","DOI":"10.1109\/SFCS.1988.21938"},{"key":"1_CR6","doi-asserted-by":"publisher","unstructured":"Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: FOCS (1991). https:\/\/doi.org\/10.1109\/SFCS.1991.185377","DOI":"10.1109\/SFCS.1991.185377"},{"key":"1_CR7","doi-asserted-by":"publisher","unstructured":"Balliu, A., Hirvonen, J., Korhonen, J.H., Lempi\u00e4inen, T., Olivetti, D., Suomela, J.: New classes of distributed time complexity. In: STOC (2018). https:\/\/doi.org\/10.1145\/3188745.3188860","DOI":"10.1145\/3188745.3188860"},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-030-24922-9_3","volume-title":"Structural Information and Communication Complexity","author":"A Balliu","year":"2019","unstructured":"Balliu, A., Hirvonen, J., Lenzen, C., Olivetti, D., Suomela, J.: Locality of not-so-weak coloring. In: Censor-Hillel, K., Flammini, M. (eds.) SIROCCO 2019. LNCS, vol. 11639, pp. 37\u201351. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-24922-9_3"},{"key":"1_CR9","unstructured":"Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., Suomela, J.: Local mending (2022). https:\/\/arxiv.org\/abs\/2102.08703"},{"key":"1_CR10","doi-asserted-by":"publisher","unstructured":"Barenboim, L.: Deterministic $$(\\Delta + 1)$$-coloring in sublinear (in $$\\Delta $$) time in static, dynamic, and faulty networks. J. ACM 63(5) (2016). https:\/\/doi.org\/10.1145\/2979675","DOI":"10.1145\/2979675"},{"key":"1_CR11","doi-asserted-by":"publisher","DOI":"10.2200\/S00520ED1V01Y201307DCT011","author":"L Barenboim","year":"2013","unstructured":"Barenboim, L., Elkin, M.: Distributed graph coloring: fundamentals and recent developments. Morgan Claypool (2013). https:\/\/doi.org\/10.2200\/S00520ED1V01Y201307DCT011","journal-title":"Morgan Claypool"},{"key":"1_CR12","doi-asserted-by":"publisher","unstructured":"Brandt, S., et al.: A lower bound for the distributed Lov\u00e1sz local lemma. In: STOC (2016). https:\/\/doi.org\/10.1145\/2897518.2897570","DOI":"10.1145\/2897518.2897570"},{"key":"1_CR13","doi-asserted-by":"publisher","unstructured":"Brandt, S., et al.: LCL problems on grids. In: PODC (2017). https:\/\/doi.org\/10.1145\/3087801.3087833","DOI":"10.1145\/3087801.3087833"},{"key":"1_CR14","doi-asserted-by":"publisher","unstructured":"Censor-Hillel, K., Dafni, N., Kolobov, V.I., Paz, A., Schwartzman, G.: Fast deterministic algorithms for highly-dynamic networks. In: OPODIS (2021). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2020.28","DOI":"10.4230\/LIPIcs.OPODIS.2020.28"},{"key":"1_CR15","doi-asserted-by":"publisher","unstructured":"Chang, Y.J., He, Q., Li, W., Pettie, S., Uitto, J.: The complexity of distributed edge coloring with small palettes. In: SODA (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.168","DOI":"10.1137\/1.9781611975031.168"},{"key":"1_CR16","doi-asserted-by":"publisher","unstructured":"Chang, Y.J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. In: FOCS (2016). https:\/\/doi.org\/10.1109\/FOCS.2016.72","DOI":"10.1109\/FOCS.2016.72"},{"issue":"1","key":"1_CR17","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/17M1157957","volume":"48","author":"YJ Chang","year":"2019","unstructured":"Chang, Y.J., Pettie, S.: A time hierarchy theorem for the LOCAL model. SIAM J. Comput. 48(1), 33\u201369 (2019). https:\/\/doi.org\/10.1137\/17M1157957","journal-title":"SIAM J. Comput."},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-030-79527-6_3","volume-title":"Structural Information and Communication Complexity","author":"Y-J Chang","year":"2021","unstructured":"Chang, Y.-J., Studen\u00fd, J., Suomela, J.: Distributed graph problems through an\u00a0automata-theoretic lens. In: Jurdzi\u0144ski, T., Schmid, S. (eds.) SIROCCO 2021. LNCS, vol. 12810, pp. 31\u201349. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-79527-6_3"},{"key":"1_CR19","doi-asserted-by":"publisher","unstructured":"Chechik, S., Mukhtar, D.: Optimal distributed coloring algorithms for planar graphs in the LOCAL model. In: SODA (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.49","DOI":"10.1137\/1.9781611975482.49"},{"issue":"6","key":"1_CR20","doi-asserted-by":"publisher","first-page":"2232","DOI":"10.1137\/080732109","volume":"39","author":"F Chierichetti","year":"2010","unstructured":"Chierichetti, F., Vattani, A.: The local nature of list colorings for graphs of high girth. SIAM J. Comput. 39(6), 2232\u20132250 (2010). https:\/\/doi.org\/10.1137\/080732109","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1_CR21","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1002\/net.3230100304","volume":"10","author":"EJ Cockayne","year":"1980","unstructured":"Cockayne, E.J., Dawes, R.M., Hedetniemi, S.T.: Total domination in graphs. Networks 10(3), 211\u2013219 (1980). https:\/\/doi.org\/10.1002\/net.3230100304","journal-title":"Networks"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. In: Algorithms and Theory of Computation Handbook: General Concepts and Techniques, chap. 9 (2010)","DOI":"10.1201\/9781584888239-c9"},{"issue":"11","key":"1_CR23","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"EW Dijkstra","year":"1974","unstructured":"Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643\u2013644 (1974). https:\/\/doi.org\/10.1145\/361179.361202","journal-title":"Commun. ACM"},{"key":"1_CR24","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/6156.001.0001","volume-title":"Self-Stabilization","author":"S Dolev","year":"2000","unstructured":"Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)"},{"key":"1_CR25","unstructured":"Erd\u0151s, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proceedings West Coast Conference on Combinatorics, Graph Theory and Computing (1980)"},{"key":"1_CR26","doi-asserted-by":"publisher","unstructured":"Foerster, K.T., Korhonen, J.H., Paz, A., Rybicki, J., Schmid, S.: Input-dynamic distributed algorithms for communication networks. In: SIGMETRICS (2021). https:\/\/doi.org\/10.1145\/3410220.3453923","DOI":"10.1145\/3410220.3453923"},{"issue":"1","key":"1_CR27","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s00446-007-0032-2","volume":"20","author":"S Ghosh","year":"2007","unstructured":"Ghosh, S., Gupta, A., Herman, T., Pemmaraju, S.V.: Fault-containing self-stabilizing distributed protocols. Distrib. Comput. 20(1), 53\u201373 (2007). https:\/\/doi.org\/10.1007\/s00446-007-0032-2","journal-title":"Distrib. Comput."},{"key":"1_CR28","doi-asserted-by":"publisher","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs. In: PODC (2011). https:\/\/doi.org\/10.1145\/1993806.1993829","DOI":"10.1145\/1993806.1993829"},{"key":"1_CR29","doi-asserted-by":"publisher","unstructured":"Harris, D.G., Su, H.H., Vu, H.T.: On the locality of Nash-Williams forest decomposition and star-forest decomposition. In: PODC (2021). https:\/\/doi.org\/10.1145\/3465084.3467908","DOI":"10.1145\/3465084.3467908"},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-319-73117-9_3","volume-title":"SOFSEM 2018: Theory and Practice of Computer Science","author":"M Henzinger","year":"2018","unstructured":"Henzinger, M.: The state of the art in dynamic graph algorithms. In: Tjoa, A.M., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds.) SOFSEM 2018. LNCS, vol. 10706, pp. 40\u201344. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73117-9_3"},{"issue":"5","key":"1_CR31","doi-asserted-by":"publisher","first-page":"2867","DOI":"10.1214\/16-AOP1127","volume":"45","author":"AE Holroyd","year":"2017","unstructured":"Holroyd, A.E., Schramm, O., Wilson, D.B.: Finitary coloring. Ann. Probab. 45(5), 2867\u20132898 (2017). https:\/\/doi.org\/10.1214\/16-AOP1127","journal-title":"Ann. Probab."},{"key":"1_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/978-3-319-03850-6_14","volume-title":"Principles of Distributed Systems","author":"M K\u00f6nig","year":"2013","unstructured":"K\u00f6nig, M., Wattenhofer, R.: On local fixing. In: Baldoni, R., Nisse, N., van Steen, M. (eds.) OPODIS 2013. LNCS, vol. 8304, pp. 191\u2013205. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-03850-6_14"},{"key":"1_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/11947950_12","volume-title":"Distributed Computing and Networking","author":"A Korman","year":"2006","unstructured":"Korman, A., Kutten, S.: On distributed verification. In: Chaudhuri, S., Das, S.R., Paul, H.S., Tirthapura, S. (eds.) ICDCN 2006. LNCS, vol. 4308, pp. 100\u2013114. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11947950_12"},{"issue":"4","key":"1_CR34","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00446-007-0025-1","volume":"20","author":"A Korman","year":"2007","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distrib. Comput. 20(4), 253\u2013266 (2007). https:\/\/doi.org\/10.1007\/s00446-007-0025-1","journal-title":"Distrib. Comput."},{"issue":"4","key":"1_CR35","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.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010). https:\/\/doi.org\/10.1007\/s00446-010-0095-3","journal-title":"Distrib. Comput."},{"issue":"4","key":"1_CR36","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00453-008-9226-7","volume":"57","author":"A Korman","year":"2010","unstructured":"Korman, A., Peleg, D., Rodeh, Y.: Constructing labeling schemes through universal matrices. Algorithmica 57(4), 641\u2013652 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9226-7","journal-title":"Algorithmica"},{"issue":"1","key":"1_CR37","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1006\/jagm.1998.0972","volume":"30","author":"S Kutten","year":"1999","unstructured":"Kutten, S., Peleg, D.: Fault-local distributed mending. J. Algorithms 30(1), 144\u2013165 (1999). https:\/\/doi.org\/10.1006\/jagm.1998.0972","journal-title":"J. Algorithms"},{"issue":"1","key":"1_CR38","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1137\/S0097539797319109","volume":"30","author":"S Kutten","year":"2000","unstructured":"Kutten, S., Peleg, D.: Tight fault locality. SIAM J. Comput. 30(1), 247\u2013268 (2000). https:\/\/doi.org\/10.1137\/S0097539797319109","journal-title":"SIAM J. Comput."},{"key":"1_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-05118-0_2","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"C Lenzen","year":"2009","unstructured":"Lenzen, C., Suomela, J., Wattenhofer, R.: Local algorithms: self-stabilization on speed. In: Guerraoui, R., Petit, F. (eds.) SSS 2009. LNCS, vol. 5873, pp. 17\u201334. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-05118-0_2"},{"issue":"1","key":"1_CR40","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 J. Comput. 21(1), 193\u2013201 (1992). https:\/\/doi.org\/10.1137\/0221015","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1_CR41","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. Comput. 24(6), 1259\u20131277 (1995). https:\/\/doi.org\/10.1137\/S0097539793254571","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1_CR42","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01200759","volume":"15","author":"A Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: The local nature of $$\\Delta $$-coloring and its algorithmic applications. Combinatorica 15(2), 255\u2013280 (1995). https:\/\/doi.org\/10.1007\/BF01200759","journal-title":"Combinatorica"},{"key":"1_CR43","doi-asserted-by":"publisher","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000). https:\/\/doi.org\/10.1137\/1.9780898719772","DOI":"10.1137\/1.9780898719772"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-09993-9_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T20:13:16Z","timestamp":1656101596000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-09993-9_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031099922","9783031099939"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-09993-9_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"25 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paderborn","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2022.cs.uni-paderborn.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}