{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:55:07Z","timestamp":1781078107641,"version":"3.54.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T00:00:00Z","timestamp":1479686400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2017,8]]},"DOI":"10.1007\/s00446-016-0287-6","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T09:33:36Z","timestamp":1479720816000},"page":"261-280","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":31,"title":["Distributed algorithms for the Lov\u00e1sz local lemma and graph coloring"],"prefix":"10.1007","volume":"30","author":[{"given":"Kai-Min","family":"Chung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3838-8349","authenticated-orcid":false,"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,11,21]]},"reference":[{"issue":"4","key":"287_CR1","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1002\/rsa.3240020403","volume":"2","author":"N Alon","year":"1991","unstructured":"Alon, N.: A parallel algorithmic version of the local lemma. Random Struct. Algorithms 2(4), 367\u2013378 (1991)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"287_CR2","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","key":"287_CR3","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jctb.1999.1910","volume":"77","author":"N Alon","year":"1999","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Coloring graphs with sparse neighborhoods. J. Comb. Theory Ser. B 77(1), 73\u201382 (1999)","journal-title":"J. Comb. Theory Ser. B"},{"key":"287_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02009-4","volume-title":"Distributed Graph Coloring: Fundamentals and Recent Developments Synthesis Lectures on Distributed Computing Theory","author":"L Barenboim","year":"2013","unstructured":"Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, San Rafael (2013)"},{"issue":"1","key":"287_CR5","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2014","unstructured":"Barenboim, L., Elkin, M., Kuhn, F.: Distributed $${({\\varDelta }+1)}$$ ( \u0394 + 1 ) -coloring in linear (in $${\\varDelta }$$ \u0394 ) time. SIAM J. Comput. 43(1), 72\u201395 (2014)","journal-title":"SIAM J. Comput."},{"key":"287_CR6","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 1\u201320 (2016)","DOI":"10.1145\/2903137"},{"issue":"4","key":"287_CR7","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the Lov\u00e1sz local lemma. I. Random Struct. Algorithms 2(4), 343\u2013365 (1991)","journal-title":"Random Struct. Algorithms"},{"key":"287_CR8","doi-asserted-by":"crossref","unstructured":"Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempi\u00e4inen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed lov\u00e1sz local lemma. In: Proceedings of 48th ACM Symposium on Theory of Computing (STOC), pp. 479\u2013488 (2016)","DOI":"10.1145\/2897518.2897570"},{"issue":"6","key":"287_CR9","doi-asserted-by":"crossref","first-page":"2132","DOI":"10.1137\/100799642","volume":"42","author":"K Chandrasekaran","year":"2013","unstructured":"Chandrasekaran, K., Goyal, N., Haeupler, B.: Deterministic algorithms for the Lov\u00e1sz local lemma. SIAM J. Comput. 42(6), 2132\u20132155 (2013)","journal-title":"SIAM J. Comput."},{"key":"287_CR10","doi-asserted-by":"crossref","unstructured":"Chang, Y., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. In: Proceedings of 57th Symposium on Foundations of Computer Science (FOCS), pp. 195\u2013197 (2016)","DOI":"10.1109\/FOCS.2016.72"},{"key":"287_CR11","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Scheideler, C.: A new algorithm approach to the general Lov\u00e1sz local lemma with applications to scheduling and satisfiability problems (extended abstract). In: Proceedings of 32nd ACM Symposium on Theory of Computing (STOC), pp. 38\u201347 (2000)","DOI":"10.1145\/335305.335310"},{"issue":"2","key":"287_CR12","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0304-3975(98)00022-X","volume":"203","author":"D Dubhashi","year":"1998","unstructured":"Dubhashi, D., Grable, D.A., Panconesi, A.: Near-optimal, distributed edge colouring via the nibble method. Theor. Comput. Sci. 203(2), 225\u2013251 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"287_CR13","doi-asserted-by":"crossref","unstructured":"Elkin, M., Pettie, S., Su, H.-H.: ( $$2{\\varDelta }-1$$ 2 \u0394 - 1 )-edge-coloring is much easier than maximal matching in the distributed setting. In: Proceedings of 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 355\u2013370 (2015)","DOI":"10.1137\/1.9781611973730.26"},{"key":"287_CR14","first-page":"609","volume-title":"Infinite and Finite Sets","author":"P Erd\u0151s","year":"1975","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Hanjal, A., Rado, R., S\u00f3s, V.T. (eds.) Infinite and Finite Sets, vol. 11, pp. 609\u2013627. North-Holland, Amsterdam (1975)"},{"key":"287_CR15","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 270\u2013277 (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"issue":"6","key":"287_CR16","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/2049697.2049702","volume":"58","author":"B Haeupler","year":"2011","unstructured":"Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the Lov\u00e1sz local lemma. J. ACM 58(6), 28 (2011)","journal-title":"J. ACM"},{"key":"287_CR17","doi-asserted-by":"crossref","unstructured":"Harris, D.G.: Lopsidependency in the Moser\u2013Tardos framework: beyond the lopsided Lov\u00e1sz local lemma. In: Proceedings of 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1792\u20131808 (2015)","DOI":"10.1137\/1.9781611973730.120"},{"key":"287_CR18","doi-asserted-by":"crossref","unstructured":"Harris, D.G., Srinivasan, A.: The Moser-Tardos framework with partial resampling. In: Proceedings of 54th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 469\u2013478 (2013)","DOI":"10.1109\/FOCS.2013.57"},{"key":"287_CR19","doi-asserted-by":"crossref","unstructured":"Harris, D.G., Srinivasan, A.: A constructive algorithm for the Lov\u00e1sz local lemma on permutations. In: Proceedings of 25th ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 907\u2013925 (2014)","DOI":"10.1137\/1.9781611973402.68"},{"issue":"4","key":"287_CR20","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1017\/S0963548301004758","volume":"10","author":"PE Haxell","year":"2001","unstructured":"Haxell, P.E.: A note on vertex list colouring. Comb. Probab. Comput. 10(4), 345\u2013347 (2001)","journal-title":"Comb. Probab. Comput."},{"issue":"4","key":"287_CR21","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/BF01195001","volume":"17","author":"H Hind","year":"1997","unstructured":"Hind, H., Molloy, M., Reed, B.: Colouring a graph frugally. Combinatorica 17(4), 469\u2013482 (1997)","journal-title":"Combinatorica"},{"key":"287_CR22","doi-asserted-by":"crossref","unstructured":"Kolipaka, K., Szegedy, M.: Moser and Tardos meet Lov\u00e1sz. In: Proceedings 43rd ACM Symposium on Theory of Computing (STOC), pp. 235\u2013244 (2011)","DOI":"10.1145\/1993636.1993669"},{"issue":"2","key":"287_CR23","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/2742012","volume":"63","author":"F Kuhn","year":"2016","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63(2), 17 (2016)","journal-title":"J. ACM"},{"key":"287_CR24","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 7\u201315 (2006)","DOI":"10.1145\/1146381.1146387"},{"key":"287_CR25","doi-asserted-by":"crossref","unstructured":"Levi, R., Rubinfeld, R., Yodpinyanee, A.: Local computation algorithms for graphs of non-constant degrees. Algorithmica, pp. 1\u201324 (2016)","DOI":"10.1007\/s00453-016-0126-y"},{"issue":"1","key":"287_CR26","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."},{"issue":"4","key":"287_CR27","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(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"287_CR28","doi-asserted-by":"crossref","unstructured":"Molloy, M., Reed, B.: Further algorithmic aspects of the local lemma. In: Proceedings of 30th ACM Symposium on Theory of Computing (STOC), pp. 524\u2013529 (1998)","DOI":"10.1145\/276698.276866"},{"key":"287_CR29","volume-title":"Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics","author":"M Molloy","year":"2001","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics. Springer, Berlin (2001)"},{"issue":"2","key":"287_CR30","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1016\/j.jctb.2009.07.002","volume":"100","author":"M Molloy","year":"2010","unstructured":"Molloy, M., Reed, B.: Asymptotically optimal frugal colouring. J. Comb. Theory Ser. B 100(2), 226\u2013246 (2010)","journal-title":"J. Comb. Theory Ser. B"},{"key":"287_CR31","unstructured":"Moser, R.A.: Derandomizing the Lov\u00e1sz local lemma more effectively. CoRR, abs\/0807.2120 (2008)"},{"key":"287_CR32","doi-asserted-by":"crossref","unstructured":"Moser, R.A.: A constructive proof of the Lov\u00e1sz local lemma. In: Proceedings of 41st ACM Symposium on Theory of Computing (STOC), pp. 343\u2013350 (2009)","DOI":"10.1145\/1536414.1536462"},{"issue":"2","key":"287_CR33","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1667053.1667060","volume":"57","author":"RA Moser","year":"2010","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general Lov\u00e1sz local lemma. J. ACM 57(2), 11 (2010)","journal-title":"J. ACM"},{"issue":"2","key":"287_CR34","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1137\/110828290","volume":"28","author":"W Pegden","year":"2014","unstructured":"Pegden, W.: An extension of the Moser\u2013Tardos algorithmic local lemma. SIAM J. Discrete Math. 28(2), 911\u2013917 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"287_CR35","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"287_CR36","doi-asserted-by":"crossref","unstructured":"Pemmaraju, S., Srinivasan, A.: The randomized coloring procedure with symmetry-breaking. In: Proceedings of 35th Int\u2019l Colloq. on Automata, Languages, and Programming (ICALP), pp. 306\u2013319 (2008)","DOI":"10.1007\/978-3-540-70575-8_26"},{"key":"287_CR37","doi-asserted-by":"crossref","unstructured":"Pettie, S., Su, H.-H.: Fast distributed coloring algorithms for triangle-free graphs. In: Proceedings of 40th Int\u2019l Colloq. on Automata, Languages, and Programming (ICALP), pp. 687\u2013699, (2013)","DOI":"10.1007\/978-3-642-39212-2_59"},{"issue":"2","key":"287_CR38","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<149::AID-JGT8>3.0.CO;2-#","volume":"31","author":"B Reed","year":"1999","unstructured":"Reed, B.: The list colouring constants. J. Graph Theory 31(2), 149\u2013153 (1999)","journal-title":"J. Graph Theory"},{"key":"287_CR39","unstructured":"Reed, B., Sudakov, B.: Asymptotically the list colouring constants are 1. J. Comb. Theory Ser. B 86(1), 27\u201337 (2002)"},{"key":"287_CR40","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A new technique for distributed symmetry breaking. In: Proceedings of 29th ACM Symposium on Principles of Distributed Computing (PODC), pp. 257\u2013266 (2010)","DOI":"10.1145\/1835698.1835760"},{"key":"287_CR41","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0012-365X(77)90044-9","volume":"20","author":"J Spencer","year":"1977","unstructured":"Spencer, J.: Asymptotic lower bounds for Ramsey functions. Discret. Math. 20, 69\u201376 (1977)","journal-title":"Discret. Math."},{"key":"287_CR42","unstructured":"Srinivasan, A.: Improved algorithmic versions of the Lov\u00e1sz local lemma. In: Proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 611\u2013620 (2008)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-016-0287-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-016-0287-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-016-0287-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,14]],"date-time":"2022-07-14T07:42:39Z","timestamp":1657784559000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-016-0287-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,21]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["287"],"URL":"https:\/\/doi.org\/10.1007\/s00446-016-0287-6","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,21]]}}}