{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:49Z","timestamp":1781078209154,"version":"3.54.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,7,5]],"date-time":"2023-07-05T00:00:00Z","timestamp":1688515200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,5]],"date-time":"2023-07-05T00:00:00Z","timestamp":1688515200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Gran Sasso Science Institute - GSSI"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,12]]},"abstract":"Abstract<\/jats:title>We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph$$G=(V,E)$$<\/jats:tex-math>G<\/mml:mi>=<\/mml:mo>(<\/mml:mo>V<\/mml:mi>,<\/mml:mo>E<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is the average over the times at which the nodesV<\/jats:italic>ofG<\/jats:italic>finish their computation and commit to their outputs. We study the node-averaged complexity for some of the central distributed symmetry breaking problems and provide the following results (among others). As our main result, we show that the randomized node-averaged complexity of computing a maximal independent set (MIS) inn<\/jats:italic>-node graphs of maximum degree$$\\Delta $$<\/jats:tex-math>\u0394<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is at least$$\\Omega \\big (\\min \\big \\{\\frac{\\log \\Delta }{\\log \\log \\Delta },\\sqrt{\\frac{\\log n}{\\log \\log n}}\\big \\}\\big )$$<\/jats:tex-math>\u03a9<\/mml:mi>(<\/mml:mo><\/mml:mrow>min<\/mml:mo>{<\/mml:mo><\/mml:mrow>log<\/mml:mo>\u0394<\/mml:mi><\/mml:mrow>log<\/mml:mo>log<\/mml:mo>\u0394<\/mml:mi><\/mml:mrow><\/mml:mfrac>,<\/mml:mo>log<\/mml:mo>n<\/mml:mi><\/mml:mrow>log<\/mml:mo>log<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:mfrac><\/mml:msqrt>}<\/mml:mo><\/mml:mrow>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This bound is obtained by a novel adaptation of the well-known lower bound by Kuhn, Moscibroda, and Wattenhofer [JACM\u201916]. As a side result, we obtain that the worst-case randomized round complexity for computing an MIS in trees is also$$\\Omega \\big (\\min \\big \\{\\frac{\\log \\Delta }{\\log \\log \\Delta },\\sqrt{\\frac{\\log n}{\\log \\log n}}\\big \\}\\big )$$<\/jats:tex-math>\u03a9<\/mml:mi>(<\/mml:mo><\/mml:mrow>min<\/mml:mo>{<\/mml:mo><\/mml:mrow>log<\/mml:mo>\u0394<\/mml:mi><\/mml:mrow>log<\/mml:mo>log<\/mml:mo>\u0394<\/mml:mi><\/mml:mrow><\/mml:mfrac>,<\/mml:mo>log<\/mml:mo>n<\/mml:mi><\/mml:mrow>log<\/mml:mo>log<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:mfrac><\/mml:msqrt>}<\/mml:mo><\/mml:mrow>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u2014this essentially answers open problem 11.15 in the book by Barenboim and Elkin and resolves the complexity of MIS on trees up to an$$O(\\sqrt{\\log \\log n})$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>log<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:msqrt>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>factor. We also show that, perhaps surprisingly, a minimal relaxation of MIS, which is the same as (2,\u00a01)-ruling set, to the (2,\u00a02)-ruling set problem drops the randomized node-averaged complexity toO<\/jats:italic>(1). For maximal matching, we show that while the randomized node-averaged complexity is$$\\Omega \\big (\\min \\big \\{\\frac{\\log \\Delta }{\\log \\log \\Delta },\\sqrt{\\frac{\\log n}{\\log \\log n}}\\big \\}\\big )$$<\/jats:tex-math>\u03a9<\/mml:mi>(<\/mml:mo><\/mml:mrow>min<\/mml:mo>{<\/mml:mo><\/mml:mrow>log<\/mml:mo>\u0394<\/mml:mi><\/mml:mrow>log<\/mml:mo>log<\/mml:mo>\u0394<\/mml:mi><\/mml:mrow><\/mml:mfrac>,<\/mml:mo>log<\/mml:mo>n<\/mml:mi><\/mml:mrow>log<\/mml:mo>log<\/mml:mo>n<\/mml:mi><\/mml:mrow><\/mml:mfrac><\/mml:msqrt>}<\/mml:mo><\/mml:mrow>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the randomized edge-averaged complexity isO<\/jats:italic>(1). Further, we show that the deterministic edge-averaged complexity of maximal matching is$$O(\\log ^2\\Delta + \\log ^* n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>2<\/mml:mn><\/mml:msup>\u0394<\/mml:mi>+<\/mml:mo>log<\/mml:mo>\u2217<\/mml:mo><\/mml:msup>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and the deterministic node-averaged complexity of maximal matching is$$O(\\log ^3\\Delta + \\log ^* n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>3<\/mml:mn><\/mml:msup>\u0394<\/mml:mi>+<\/mml:mo>log<\/mml:mo>\u2217<\/mml:mo><\/mml:msup>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be$$\\Theta (\\log n)$$<\/jats:tex-math>\u0398<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity$$O(\\log ^* n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>\u2217<\/mml:mo><\/mml:msup>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, while keeping the worst-case complexity in$$O(\\log n)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00446-023-00453-1","type":"journal-article","created":{"date-parts":[[2023,7,5]],"date-time":"2023-07-05T15:03:01Z","timestamp":1688569381000},"page":"451-473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Node and edge averaged complexities of local graph problems"],"prefix":"10.1007","volume":"36","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,7,5]]},"reference":[{"issue":"4","key":"453_CR1","doi-asserted-by":"publisher","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"},{"key":"453_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proceedings of 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"453_CR3","unstructured":"Ahmadi, M., Kuhn, F., Oshman, R.: Distributed approximate maximum matching in the congest model. In: Proceedings of the International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"issue":"1","key":"453_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.10003","volume":"20","author":"A Amit","year":"2002","unstructured":"Amit, A., Linial, N., Matousek, J.: Random lifts of graphs: independence and chromatic number. Random Struct. Algorithms 20(1), 1\u201322 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"453_CR5","doi-asserted-by":"crossref","unstructured":"Balliu, A., Brandt, S., Kuhn, F., Oliveti, D.: Deterministic $$\\delta $$-coloring plays hide-and-seek. In: Proceedings of 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC) (2022)","DOI":"10.1145\/3519935.3520027"},{"key":"453_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-02009-4","volume-title":"Distributed Graph Coloring: Fundamentals and Recent Developments","author":"L Barenboim","year":"2013","unstructured":"Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers (2013)"},{"issue":"1","key":"453_CR7","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2014","unstructured":"Barenboim, L., Elkin, M., Kuhn, F.: Distributed $$(\\Delta +1)$$-coloring in linear (in $$\\Delta $$) time. SIAM J. Comput. 43(1), 72\u201395 (2014)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"453_CR8","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/2903137","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 20 (2016)","journal-title":"J. ACM"},{"key":"453_CR9","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 the Symposium on Theory of Computing (STOC), pp. 479\u2013488 (2016)","DOI":"10.1145\/2897518.2897570"},{"issue":"5","key":"453_CR10","doi-asserted-by":"publisher","first-page":"1735","DOI":"10.1137\/17M1158604","volume":"47","author":"MA Bender","year":"2018","unstructured":"Bender, M.A., Kopelowitz, T., Pettie, S., Young, M.: Contention resolution with constant throughput and log-logstar channel accesses. SIAM J. Comput. 47(5), 1735\u20131754 (2018)","journal-title":"SIAM J. Comput."},{"key":"453_CR11","unstructured":"Barenboim, L., Maimon, T.: Deterministic logarithmic completeness in the distributed sleeping model. In: Proceedings of 35th International Symposium on Distributed Computing (DISC), Volume 209 of LIPIcs, pp. 10:1\u201310:19 (2021)"},{"key":"453_CR12","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Tzur, Y.: Distributed symmetry-breaking with improved vertex-averaged complexity. In: Proceedings of 20th International Conference on Distributed Computing and Networking (ICDCN), pp. 31\u201340 (2019)","DOI":"10.1145\/3288599.3288601"},{"key":"453_CR13","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Censor-Hillel, K., Ghaffari, M., Schwartzman, G.: Distributed approximation of maximum independent set and maximum matching. In: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp. 165\u2013174 (2017)","DOI":"10.1145\/3087801.3087806"},{"key":"453_CR14","doi-asserted-by":"crossref","unstructured":"Chang, Y.J., Dani, V., Hayes, T.P., Pettie, S.: The energy complexity of bfs in radio networks. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 273\u2013282 (2020)","DOI":"10.1145\/3382734.3405713"},{"key":"453_CR15","doi-asserted-by":"crossref","unstructured":"Chatterjee, S., Gmyr, R., Pandurangan, G.: Sleeping is efficient: Mis in $${O}(1)$$-rounds node-averaged awake complexity. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 99\u2013108 (2020)","DOI":"10.1145\/3382734.3405718"},{"key":"453_CR16","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. In: Proceedings of 57th IEEE Symposium on Foundations of Computer Science (FOCS) (2016)","DOI":"10.1109\/FOCS.2016.72"},{"issue":"4","key":"453_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3341111","volume":"15","author":"Y-J Chang","year":"2019","unstructured":"Chang, Y.-J., Kopelowitz, T., Pettie, S., Wang, R., Zhan, W.: Exponential separations in the energy complexity of leader election. ACM Trans. Algorithms 15(4), 1\u201331 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"453_CR18","doi-asserted-by":"crossref","unstructured":"Coupette, C., Lenzen, C.: A breezing proof of the KMW bound. In: 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11\u201312, 2021, pp. 184\u2013195. SIAM (2021)","DOI":"10.1137\/1.9781611976472.21"},{"key":"453_CR19","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Li, W., Pettie, S.: An optimal distributed $$(\\Delta + 1) $$-coloring algorithm? In: Proceedings of 50th ACM Symposium on Theory of Computing (STOC) (2018)","DOI":"10.1145\/3188745.3188964"},{"key":"453_CR20","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2019.01.023","volume":"811","author":"L Feuilloley","year":"2020","unstructured":"Feuilloley, L.: How long it takes for an ordinary node with an ordinary id to output? Theoret. Comput. Sci. 811, 42\u201355 (2020)","journal-title":"Theoret. Comput. Sci."},{"key":"453_CR21","unstructured":"Fischer, M., Ghaffari, M.: Sublogarithmic distributed algorithms for lov\u00e1sz local lemma, and the complexity hierarchy. arXiv preprint arXiv:1705.04840 (2017)"},{"key":"453_CR22","doi-asserted-by":"crossref","unstructured":"Fischer, M.: Improved deterministic distributed matching via rounding. Distrib. Comput. 33(3), 279\u2013291 (2020)","DOI":"10.1007\/s00446-018-0344-4"},{"key":"453_CR23","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"},{"key":"453_CR24","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Harris, D., Kuhn, F.: On derandomizing local distributed algorithms. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 662\u2013673 (2018)","DOI":"10.1109\/FOCS.2018.00069"},{"key":"453_CR25","unstructured":"Ghaffari, M., Kuhn, F.: Deterministic distributed vertex coloring: simpler, faster, and without network decomposition. In: Proceedings of 62nd IEEE Symposium on Foundations of Computer Science (FOCS) (2021)"},{"key":"453_CR26","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Su, H.-H.: Distributed degree splitting, edge coloring, and orientations. In: Proceedings of 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2505\u20132523 (2017)","DOI":"10.1137\/1.9781611974782.166"},{"key":"453_CR27","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Su, H.-H.: Distributed degree splitting, edge coloring, and orientations. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2505\u20132523. Society for Industrial and Applied Mathematics (2017)","DOI":"10.1137\/1.9781611974782.166"},{"key":"453_CR28","doi-asserted-by":"crossref","unstructured":"Harris, D.G., Schneider, J., Su, H.H.: Distributed ($$\\delta $$+ 1)-coloring in sublogarithmic rounds. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pp. 465\u2013478 (2016)","DOI":"10.1145\/2897518.2897533"},{"issue":"2","key":"453_CR29","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 77\u201380 (1986)","journal-title":"Inf. Process. Lett."},{"key":"453_CR30","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, T., Kuty\u0142owski, M., Zatopia\u0144ski, J.: Efficient algorithms for leader election in radio networks. In: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, pp. 51\u201357 (2002)","DOI":"10.1145\/571825.571833"},{"key":"453_CR31","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, T., Kuty\u0142owski, M., Zatopia\u0144ski, J.: Energy-efficient size approximation of radio networks with no collision detection. In: International Computing and Combinatorics Conference, pp. 279\u2013289. Springer (2002)","DOI":"10.1007\/3-540-45655-4_31"},{"issue":"5","key":"453_CR32","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0020-0190(99)00064-2","volume":"70","author":"\u00d6 Johansson","year":"1999","unstructured":"Johansson, \u00d6.: Simple distributed $$\\Delta +1$$-coloring of graphs. Inf. Process. Lett. 70(5), 229\u2013232 (1999)","journal-title":"Inf. Process. Lett."},{"key":"453_CR33","doi-asserted-by":"crossref","unstructured":"Kardas, M., Klonowski, M., Pajak, D.: Energy-efficient leader election protocols for single-hop radio networks. In: Proceedings of 42nd International Conference on Parallel Processing (ICPP), pp. 399\u2013408 (2013)","DOI":"10.1109\/ICPP.2013.49"},{"key":"453_CR34","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"453_CR35","doi-asserted-by":"publisher","first-page":"2","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 (2016)","journal-title":"J. ACM"},{"issue":"1","key":"453_CR36","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S Kutten","year":"1998","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of smallk-dominating sets and applications. J. Algorithms 28(1), 40\u201366 (1998)","journal-title":"J. Algorithms"},{"key":"453_CR37","doi-asserted-by":"crossref","unstructured":"Linial, N.: Distributive graph algorithms\u2014global solutions from local data. In: Proceedings of 28th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 331\u2013335 (1987)","DOI":"10.1109\/SFCS.1987.20"},{"key":"453_CR38","doi-asserted-by":"publisher","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, 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"453_CR39","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/0022-0000(93)90033-S","volume":"47","author":"M Luby","year":"1993","unstructured":"Luby, M.: Removing randomness in parallel computation without a processor penalty. J. Comput. Syst. Sci. 47(2), 250\u2013286 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"453_CR40","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1137\/0404036","volume":"4","author":"M Naor","year":"1991","unstructured":"Naor, M.: A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Math. 4(3), 409\u2013412 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"8","key":"453_CR41","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1109\/71.877942","volume":"11","author":"K Nakano","year":"2000","unstructured":"Nakano, K., Olariu, S.: Energy-efficient initialization protocols for single-hop radio networks with no collision detection. IEEE Trans. Parallel Distrib. Syst. 11(8), 851\u2013863 (2000)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"453_CR42","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"453_CR43","unstructured":"Rozhon, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: Proceedings of 52nd ACM Symposium on Theory of Computing (STOC)"},{"key":"453_CR44","doi-asserted-by":"crossref","unstructured":"Schneider, J., Elkin, M., Wattenhofer, R.: Symmetry breaking depending on the chromatic number or the neighborhood growth. Theoret. Comput. Sci. 509, 40\u201350 (2013)","DOI":"10.1016\/j.tcs.2012.09.004"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00453-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-023-00453-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-023-00453-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T18:10:13Z","timestamp":1729707013000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-023-00453-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,5]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["453"],"URL":"https:\/\/doi.org\/10.1007\/s00446-023-00453-1","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,5]]},"assertion":[{"value":"15 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}