{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:50Z","timestamp":1750694750200,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T00:00:00Z","timestamp":1549238400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004757","name":"Ulla Tuominen Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004757","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["336495","336495"],"award-info":[{"award-number":["336495","336495"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["336495"],"award-info":[{"award-number":["336495"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Research Council","award":["336495"],"award-info":[{"award-number":["336495"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00446-018-00346-8","type":"journal-article","created":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T05:55:40Z","timestamp":1549259740000},"page":"293-310","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Improved distributed degree splitting and edge coloring"],"prefix":"10.1007","volume":"33","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[]},{"given":"Juho","family":"Hirvonen","sequence":"additional","affiliation":[]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1025-5037","authenticated-orcid":false,"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,4]]},"reference":[{"key":"346_CR1","first-page":"129","volume":"2011","author":"L Barenboim","year":"2011","unstructured":"Barenboim, L., Elkin, M.: Distributed deterministic edge coloring using bounded neighborhood independence. Proc. PODC 2011, 129\u2013138 (2011)","journal-title":"Proc. PODC"},{"issue":"1","key":"346_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(81)90022-6","volume":"3","author":"J Beck","year":"1981","unstructured":"Beck, J., Fiala, T.: \u201cInteger-making\u201d theorems. Discrete Appl. Math. 3(1), 1\u20138 (1981)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"346_CR3","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01196138","volume":"17","author":"D Bednarchak","year":"1997","unstructured":"Bednarchak, D., Helm, M.: A note on the Beck\u2013Fiala theorem. Combinatorica 17(1), 147\u2013149 (1997)","journal-title":"Combinatorica"},{"key":"346_CR4","first-page":"479","volume":"2016","author":"S Brandt","year":"2016","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. Proc. STOC 2016, 479\u2013488 (2016)","journal-title":"Proc. STOC"},{"issue":"03","key":"346_CR5","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1017\/S0963548315000140","volume":"25","author":"B Bukh","year":"2016","unstructured":"Bukh, B.: An improvement of the Beck\u2013Fiala theorem. Comb. Probab. Comput. 25(03), 380\u2013398 (2016)","journal-title":"Comb. Probab. Comput."},{"key":"346_CR6","first-page":"615","volume":"2016","author":"YJ Chang","year":"2016","unstructured":"Chang, Y.J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the local model. Proc. FOCS 2016, 615\u2013624 (2016)","journal-title":"Proc. FOCS"},{"key":"346_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method: Randomness and Complexity","author":"B Chazelle","year":"2000","unstructured":"Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University Press, Cambridge (2000)"},{"key":"346_CR8","first-page":"345","volume":"2001","author":"A Czygrinow","year":"2001","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Karo\u0144ski, M.: Distributed $$O(\\Delta \\log n)$$-edge-coloring algorithm. Proc. ESA 2001, 345\u2013355 (2001)","journal-title":"Proc. ESA"},{"key":"346_CR9","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/11685654_10","volume-title":"Theoretical Computer Science, Essays in Memory of Shimon Even","author":"Y Dinitz","year":"2006","unstructured":"Dinitz, Y.: Dinitz\u2019 algorithm: the original version and Even\u2019s version. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science, Essays in Memory of Shimon Even, pp. 218\u2013240. Springer, Berlin (2006)"},{"key":"346_CR10","unstructured":"Fischer, M., Ghaffari, M., Kuhn, F.: Deterministic distributed edge-coloring via hypergraph maximal matching. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, 2017, pp. 180\u2013191 (2017)"},{"key":"346_CR11","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Harris, D.G., Kuhn, F.: On derandomizing local distributed algorithms. In: 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2018)","DOI":"10.1109\/FOCS.2018.00069"},{"key":"346_CR12","unstructured":"Ghaffari, M., Hirvonen, J., Kuhn, F., Maus, Y., Suomela, J., Uitto, J.: Improved distributed degree splitting and edge coloring. In: Proceedings of the 31st Symposium on Distributed Computing (DISC), pp. 19:1\u201319:15 (2017)"},{"key":"346_CR13","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y., Uitto, J.: Deterministic distributed edge-coloring with fewer colors. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25\u201329, 2018, pp. 418\u2013430 (2018)"},{"key":"346_CR14","first-page":"2505","volume":"2017","author":"M Ghaffari","year":"2017","unstructured":"Ghaffari, M., Su, H.H.: Distributed degree splitting, edge coloring, and orientations. Proc. SODA 2017, 2505\u20132523 (2017)","journal-title":"Proc. SODA"},{"issue":"1","key":"346_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0895480100373121","volume":"15","author":"M Ha\u0144\u0107kowiak","year":"2001","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. SIAM J. Discrete Math. 15(1), 41\u201357 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"346_CR16","doi-asserted-by":"crossref","unstructured":"Harris, D.G.: Distributed approximation algorithms for maximum matching in graphs and hypergraphs. ArXiv e-prints (2018)","DOI":"10.1109\/FOCS.2019.00048"},{"issue":"2","key":"346_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(86)90141-9","volume":"22","author":"A Israeli","year":"1986","unstructured":"Israeli, A., Shiloach, Y.: An improved parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 57\u201360 (1986)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"346_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0196-6774(87)90026-5","volume":"8","author":"HJ Karloff","year":"1987","unstructured":"Karloff, H.J., Shmoys, D.B.: Efficient parallel algorithms for edge coloring problems. J. Algorithms 8(1), 39\u201352 (1987)","journal-title":"J. Algorithms"},{"key":"346_CR19","first-page":"331","volume":"1987","author":"N Linial","year":"1987","unstructured":"Linial, N.: Distributive graph algorithms\u2014global solutions from local data. Proc. FOCS 1987, 331\u2013335 (1987)","journal-title":"Proc. FOCS"},{"key":"346_CR20","first-page":"184","volume":"1993","author":"M Naor","year":"1993","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? Proc. STOC 1993, 184\u2013193 (1993)","journal-title":"Proc. STOC"},{"issue":"2","key":"346_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/PL00008932","volume":"14","author":"A Panconesi","year":"2001","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97\u2013100 (2001)","journal-title":"Distrib. Comput."},{"key":"346_CR22","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.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-018-00346-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-00346-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-00346-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,10]],"date-time":"2020-05-10T05:03:17Z","timestamp":1589086997000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-018-00346-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,4]]},"references-count":22,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["346"],"URL":"https:\/\/doi.org\/10.1007\/s00446-018-00346-8","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2019,2,4]]},"assertion":[{"value":"18 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}