{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T13:08:44Z","timestamp":1783170524300,"version":"3.54.6"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T00:00:00Z","timestamp":1573776000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC","award":["336495 (ACDC)"],"award-info":[{"award-number":["336495 (ACDC)"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1514383, CCF-1637546, and CCF-1815316"],"award-info":[{"award-number":["CCF-1514383, CCF-1637546, and CCF-1815316"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,1,31]]},"abstract":"<jats:p>\n            The complexity of distributed edge coloring depends heavily on the\n            <jats:italic>palette size<\/jats:italic>\n            as a function of the maximum degree \u0394. In this article, we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows.\n          <\/jats:p>\n          <jats:p>\n            <jats:bold>Lower Bounds:<\/jats:bold>\n            First, we simplify the\n            <jats:italic>round elimination<\/jats:italic>\n            technique of Brandt et al.\u00a0[16] and prove that (2\u0394 \u22122)-edge coloring requires \u03a9 (log\n            <jats:sub>\u0394<\/jats:sub>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time with high probability\u00a0and \u03a9 (log\n            <jats:sub>\u0394<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            ) time deterministically,\n            <jats:italic>even on trees<\/jats:italic>\n            . Second, we show that a natural approach to computing (\u0394 +1)-edge colorings (Vizing\u2019s theorem), namely, extending an arbitrary partial coloring by iteratively recoloring subgraphs, requires \u03a9 (\u0394 log\n            <jats:italic>n<\/jats:italic>\n            ) time.\n          <\/jats:p>\n          <jats:p>\n            <jats:bold>Upper Bounds on General Graphs:<\/jats:bold>\n            We give a randomized edge coloring algorithm that can use palette sizes as small as \u0394 + \u00d5(\u221a\u0394), which is a natural barrier for randomized approaches. The running time of our (1+\u03f5)\u0394-edge coloring algorithm is usually dominated by\n            <jats:italic>O<\/jats:italic>\n            (\\log \u03f5\n            <jats:sup>\u22121<\/jats:sup>\n            ) calls to a distributed Lov\u00e1sz local lemma (LLL) algorithm. For example, using the Chung-Pettie-Su LLL algorithm, we compute a (1+\u03f5)\u0394-edge coloring in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time when \u03f5 \u2265 (log\n            <jats:sup>3<\/jats:sup>\n            \u0394) \/ \u221a \u0394 , or\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sub>\u0394<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            ) + (log log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>\n              3 +\n              <jats:italic>o<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            time when \u03f5 = \u03a9 (1). When \u0394 is sublogarithmic in\n            <jats:italic>n<\/jats:italic>\n            the performance is improved with the Ghaffari-Harris-Kuhn LLL algorithm.\n          <\/jats:p>\n          <jats:p>\n            <jats:bold>Upper Bounds on Trees:<\/jats:bold>\n            We show that the \u03a9 (log\n            <jats:sub>\u0394<\/jats:sub>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lov\u00e1sz local lemma algorithm for\n            <jats:italic>tree-structured dependency graphs<\/jats:italic>\n            , which arise naturally from\n            <jats:italic>O<\/jats:italic>\n            (1)-round probabilistic algorithms run on trees. Specifically, our (1+\u03f5)\u0394-edge coloring algorithm for trees takes\n            <jats:italic>O<\/jats:italic>\n            (log (1 \/ \u03f5)) \u22c5 max { log log\n            <jats:italic>n<\/jats:italic>\n            \\ log log log\n            <jats:italic>n<\/jats:italic>\n            , log\n            <jats:sub>log \u0394<\/jats:sub>\n            log\n            <jats:italic>n<\/jats:italic>\n            } time when \u03f5 \u2265 (log\n            <jats:sup>3<\/jats:sup>\n            \u0394) \/ \u221a \u0394, or\n            <jats:italic>O<\/jats:italic>\n            (max { log log\n            <jats:italic>n<\/jats:italic>\n            \\ log log log\n            <jats:italic>n<\/jats:italic>\n            , log\n            <jats:sub>\u0394<\/jats:sub>\n            log\n            <jats:italic>n<\/jats:italic>\n            }) time when \u03f5 = \u03a9 (1).\n          <\/jats:p>","DOI":"10.1145\/3365004","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T21:16:57Z","timestamp":1573852617000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Distributed Edge Coloring and a Special Case of the Constructive Lov\u00e1sz Local Lemma"],"prefix":"10.1145","volume":"16","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qizheng","family":"He","sequence":"additional","affiliation":[{"name":"IIIS, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenzheng","family":"Li","sequence":"additional","affiliation":[{"name":"IIIS, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Switzerland and University of Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,11,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_2_1","first-page":"82","article-title":"An efficient algorithm for colouring the edges of a graph with \u0394 + 1 colours. Info","volume":"20","author":"Arjomandi E.","year":"1982","journal-title":"Syst. Operat. Res."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS\u201989)","author":"Awerbuch B."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC\u201919)","author":"Balliu A."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC\u201918)","author":"Balliu A.","year":"2018"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC\u201918)","author":"Balliu A.","year":"1887"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC\u201919)","author":"Balliu A."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767410"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0167-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC\u201917)","author":"Barenboim L."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s B.","DOI":"10.1201\/b16132-57"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 48th ACM Symposium on the Theory of Computing (STOC\u201916)","author":"Brandt S."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC\u201917)","author":"Brandt S."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA\u201918)","author":"Chang Y.-J."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201918)","author":"Chang Y.-J."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157957"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0287-6"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201901)","author":"Czygrinow A."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-2897-6"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00022-X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.  D. P. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/299633.299634"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.26"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917)","author":"Fischer M."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS\u201917)","author":"Fischer M."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Fraigniaud P."},{"key":"e_1_2_1_33_1","volume-title":"Technical Report TRECIS-8501. Tohoku University.","author":"Gabow H. N.","year":"1985"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Ghaffari M."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC\u201918)","author":"Ghaffari M."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC\u201917)","author":"Ghaffari M."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC\u201917)","author":"Ghaffari M."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201918)","author":"Ghaffari M.","year":"1887"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.166"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548397003246"},{"key":"e_1_2_1_42_1","unstructured":"D. G. Harris. 2018. Distributed approximation algorithms for maximum matching in graphs and hypergraphs. CoRR abs\/1807.07645.  D. G. Harris. 2018. Distributed approximation algorithms for maximum matching in graphs and hypergraphs. CoRR abs\/1807.07645."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178120"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90026-5"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0174-8"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC\u201906)","author":"Kuhn F."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_50_1","first-page":"47","article-title":"Parallel tree contraction\u2014Part I","volume":"5","author":"Miller G. L.","year":"1989","journal-title":"Fundamentals. Adv. Comput. Res."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<376::AID-RSA10>3.0.CO;2-0"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"M. Molloy and B. Reed. 2001. Graph Colouring and the Probabilistic Method. Springer.  M. Molloy and B. Reed. 2001. Graph Colouring and the Probabilistic Method. Springer.","DOI":"10.1007\/978-3-642-04016-0"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200759"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach. SIAM.","author":"Peleg D.","year":"2000"},{"key":"e_1_2_1_60_1","first-page":"263","article-title":"Distributed algorithms for coloring triangle-free graphs. Info","volume":"243","author":"Pettie S.","year":"2015","journal-title":"Comput."},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (PODC\u201910)","author":"Schneider J."},{"key":"e_1_2_1_62_1","volume-title":"Proceedings of the 51st ACM Symposium on Theory of Computing (STOC\u201919)","author":"Su H.-H."},{"key":"e_1_2_1_63_1","volume-title":"On an estimate of the chromatic class of a p-graph. Diskret. Analiz No. 3","author":"Vizing V. G.","year":"1964"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365004","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365004","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3365004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:29Z","timestamp":1750197689000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3365004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,15]]},"references-count":63,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1,31]]}},"alternative-id":["10.1145\/3365004"],"URL":"https:\/\/doi.org\/10.1145\/3365004","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,15]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}