{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:24:36Z","timestamp":1762917876032,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,4,12]],"date-time":"2018-04-12T00:00:00Z","timestamp":1523491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-1010789, CCF-1422569, CCF-0939370, CCF-1217338 and BIO-1455983"],"award-info":[{"award-number":["CNS-1010789, CCF-1422569, CCF-0939370, CCF-1217338 and BIO-1455983"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-13-1-0042"],"award-info":[{"award-number":["FA9550-13-1-0042"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MIT and University of Michigan"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>\n            We give a new randomized distributed algorithm for (\u0394 +1)-coloring in the LOCAL model, running in\n            <jats:italic>O<\/jats:italic>\n            (\u221a log \u0394)+ 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\u221alog log\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ) rounds in a graph of maximum degree \u0394. This implies that the (\u0394 +1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds of \u03a9(min(\u221a\/log\n            <jats:italic>n<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            , \/log \u0394 log log \u0394)) by Kuhn, Moscibroda, and Wattenhofer [PODC\u201904]. Our algorithm also extends to list-coloring where the palette of each node contains \u0394 +1 colors. We extend the set of distributed symmetry-breaking techniques by performing a decomposition of graphs into dense and sparse parts.\n          <\/jats:p>","DOI":"10.1145\/3178120","type":"journal-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T12:10:20Z","timestamp":1523621420000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Distributed (\u0394 +1)-Coloring in Sublogarithmic Rounds"],"prefix":"10.1145","volume":"65","author":[{"given":"David G.","family":"Harris","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD"}]},{"given":"Johannes","family":"Schneider","sequence":"additional","affiliation":[{"name":"University of Liechtenstein, Vaduz, Liechtenstein"}]},{"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[{"name":"University of North Carolina at Charlotte, Charlotte, NC"}]}],"member":"320","published-online":{"date-parts":[[2018,4,12]]},"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","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63504"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767410"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00520ED1V01Y201307DCT011"},{"key":"e_1_2_1_6_1","volume-title":"A fast network-decomposition algorithm and its applications to constant-time distributed computation. Journal of Theoretical Computer Science","author":"Barenboim L.","year":"2016","unstructured":"L. Barenboim , M. Elkin , and C. Gavoille . A fast network-decomposition algorithm and its applications to constant-time distributed computation. Journal of Theoretical Computer Science ( 2016 ). L. Barenboim, M. Elkin, and C. Gavoille. A fast network-decomposition algorithm and its applications to constant-time distributed computation. Journal of Theoretical Computer Science (2016)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_2_1_10_1","volume-title":"The complexity of distributed edge coloring with small palettes. In arXiv preprint arXiv:1708.04290","author":"Chang Y.-J.","year":"2017","unstructured":"Y.-J. Chang , Q. He , W. Li , S. Pettie , and J. Uitto . The complexity of distributed edge coloring with small palettes. In arXiv preprint arXiv:1708.04290 , 2017 . Y.-J. Chang, Q. He, W. Li, S. Pettie, and J. Uitto. The complexity of distributed edge coloring with small palettes. In arXiv preprint arXiv:1708.04290, 2017."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.72"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.23"},{"key":"e_1_2_1_13_1","volume-title":"Proc. of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201985)","volume":"1","author":"Chlamtac I.","year":"1985","unstructured":"I. Chlamtac and S. Kutten . A spatial reuse TDMA\/FDMA for mobile multi-hop radio networks . In Proc. of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201985) . Technology : Emerging or Converging, 389--394 vol. 1 , 1985 . I. Chlamtac and S. Kutten. A spatial reuse TDMA\/FDMA for mobile multi-hop radio networks. In Proc. of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201985). Technology: Emerging or Converging, 389--394 vol. 1, 1985."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0287-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.35830"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00022-X"},{"key":"e_1_2_1_17_1","volume-title":"Symp. on Discrete Algorithms (SODA\u201915)","author":"Elkin M.","year":"2015","unstructured":"M. Elkin , S. Pettie , and H.-H. Su. (2 \u0394 &minus; 1)-edge-coloring is much easier than maximal matching in the distributed setting . In Symp. on Discrete Algorithms (SODA\u201915) , 355--370. SIAM, 2015 . M. Elkin, S. Pettie, and H.-H. Su. (2 \u0394 &minus; 1)-edge-coloring is much easier than maximal matching in the distributed setting. In Symp. on Discrete Algorithms (SODA\u201915), 355--370. SIAM, 2015."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/26.52656"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings 31st International Symposium on Distributed Computing (DISC\u201917)","author":"Fischer M.","year":"2017","unstructured":"M. Fischer and M. Ghaffari . Sublogarithmic distributed algorithms for Lov\u00e1sz local lemma with implications on complexity hierarchies . In Proceedings 31st International Symposium on Distributed Computing (DISC\u201917) , 18, 2017 . M. Fischer and M. Ghaffari. Sublogarithmic distributed algorithms for Lov\u00e1sz local lemma with implications on complexity hierarchies. In Proceedings 31st International Symposium on Distributed Computing (DISC\u201917), 18, 2017."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.73"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884455"},{"key":"e_1_2_1_22_1","volume-title":"Simple and near-optimal distributed coloring for sparse graphs. In arXiv preprint arXiv:1708.06275","author":"Ghaffari M.","year":"2017","unstructured":"M. Ghaffari and C. Lymouri . Simple and near-optimal distributed coloring for sparse graphs. In arXiv preprint arXiv:1708.06275 , 2017 . M. Ghaffari and C. Lymouri. Simple and near-optimal distributed coloring for sparse graphs. In arXiv preprint arXiv:1708.06275, 2017."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90169-4"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611467"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199705)10:3%3C385::AID-RSA6%3E3.0.CO;2-S"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1097"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_8"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332464"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00064-2"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1898953.1898978"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_2_1_36_1","volume-title":"North Holland","author":"Lov\u00e1sz L.","year":"1979","unstructured":"L. Lov\u00e1sz . Combinatorial Problems and Exercises . North Holland , 1979 . L. Lov\u00e1sz. Combinatorial Problems and Exercises. North Holland, 1979."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009820"},{"key":"e_1_2_1_39_1","volume-title":"Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics","author":"Molloy M.","year":"2001","unstructured":"M. Molloy and B. Reed . Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics . Springer , 2001 . M. Molloy and B. Reed. Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics. Springer, 2001."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.07.002"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.06.004"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129769"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.018"},{"volume-title":"Proc. of the Conference of the IEEE Computer and Communications Societies (INFOCOM\u201989)","author":"Ramaswami R.","key":"e_1_2_1_46_1","unstructured":"R. Ramaswami and K. K. Parhi . Distributed scheduling of broadcasts in a radio network . In Proc. of the Conference of the IEEE Computer and Communications Societies (INFOCOM\u201989) . Technology : Emerging or Converging, IEEE, 497--504, vol. 2, 1989. R. Ramaswami and K. K. Parhi. Distributed scheduling of broadcasts in a radio network. In Proc. of the Conference of the IEEE Computer and Communications Societies (INFOCOM\u201989). Technology: Emerging or Converging, IEEE, 497--504, vol. 2, 1989."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199804)27:4%3C%3E1.0.CO;2-7"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1891"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.004"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835760"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0097-1"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167156"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178120","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3178120","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3178120","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:55Z","timestamp":1750215775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3178120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,12]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3178120"],"URL":"https:\/\/doi.org\/10.1145\/3178120","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2018,4,12]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}