{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:48Z","timestamp":1781077788556,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,17]]},"DOI":"10.1145\/3626183.3659959","type":"proceedings-article","created":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T18:23:04Z","timestamp":1717525384000},"page":"331-343","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Broadcast in Highly Connected Networks"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-9747-7269","authenticated-orcid":false,"given":"Shashwat","family":"Chandra","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0109-2432","authenticated-orcid":false,"given":"Yi-Jun","family":"Chang","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8565-9642","authenticated-orcid":false,"given":"Michal","family":"Dory","sequence":"additional","affiliation":[{"name":"University of Haifa, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4213-9898","authenticated-orcid":false,"given":"Mohsen","family":"Ghaffari","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2775-9207","authenticated-orcid":false,"given":"Dean","family":"Leitersdorf","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Even in Sparse Networks. In Proceedings of the 30th International Symposium on Distributed Computing (DISC) (Lecture Notes in Computer Science","volume":"42","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud, Keren Censor-Hillel, and Seri Khoury. 2016. Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks. In Proceedings of the 30th International Symposium on Distributed Computing (DISC) (Lecture Notes in Computer Science, Vol. 9888), Cyril Gavoille and David Ilcinkas (Eds.). Springer, 29--42."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the 35th International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"19","author":"Anagnostides Ioannis","year":"2021","unstructured":"Ioannis Anagnostides and Themis Gouleakis. 2021. Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model. In Proceedings of the 35th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 5:1--5:19."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316326"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538565"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-019-00353-3"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3086465"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611491"},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Chandra Chekuri (Ed.). SIAM, 546--561","author":"Censor-Hillel Keren","year":"2014","unstructured":"Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. 2014. A NewPerspective on Vertex Connectivity. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Chandra Chekuri (Ed.). SIAM, 546--561."},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 31st International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"16","author":"Censor-Hillel Keren","year":"2017","unstructured":"Keren Censor-Hillel, Seri Khoury, and Ami Paz. 2017. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In Proceedings of the 31st International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 91), Andr\u00e9a W. Richa (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 10:1--10:16."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461798"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-72751-6_4"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.010"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs","volume":"18","author":"Chuzhoy Julia","year":"2020","unstructured":"Julia Chuzhoy, Merav Parter, and Zihan Tan. 2020. On Packing Low-Diameter Spanning Trees. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 168), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 33:1--33:18."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316346"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212760"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451020"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331617"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch164"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583668.3594578"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.91"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261118"},{"key":"e_1_3_2_1_25_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs","volume":"15","author":"Gawrychowski Pawel","year":"2020","unstructured":"Pawel Gawrychowski, Shay Mozes, and Oren Weimann. 2020. Minimum Cut in O(m log 2 n) Time. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 168), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 57:1--57:15."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.8"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_51"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767417"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467935"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.77"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538429"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 30th International Symposium on Distributed Computing (DISC). Springer, 158--172","author":"Haeupler Bernhard","year":"2016","unstructured":"Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. 2016. Near-optimal lowcongestion shortcuts on bounded parameter graphs. In Proceedings of the 30th International Symposium on Distributed Computing (DISC). Springer, 158--172."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212776"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520026"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451081"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2021.23"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2021.24"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2022.27"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2023.71"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332504"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585201"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.383"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"17","author":"Gregory Schwartzman Kawarabayashi","year":"2018","unstructured":"Ken-ichi Kawarabayashi and Gregory Schwartzman. 2018. Adapting Local Sequential Algorithms to the Distributed Setting. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 121), Ulrich Schmid and Josef Widder (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 35:1--35:17."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2948062"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90087-2"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488656"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767398"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_30"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"e_1_3_2_1_55_1","volume-title":"Proceedings of the 33rd International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"16","author":"Parter Merav","year":"2019","unstructured":"Merav Parter. 2019. Small Cuts and Connectivity Certificates: A Fault Tolerant Approach. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 146), Jukka Suomela (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 30:1--30:16."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538453"},{"key":"e_1_3_2_1_57_1","volume-title":"Proceedings of the 36th International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"21","author":"Parter Merav","year":"2022","unstructured":"Merav Parter and Asaf Petruschka. 2022. Near-Optimal Distributed Computation of Small Vertex Cuts. In Proceedings of the 36th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 246), Christian Scheideler (Ed.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 31:1--31:21."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.102"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331620"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_58"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000814"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520074"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/224964.224968"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.231858"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"},{"key":"e_1_3_2_1_67_1","volume-title":"Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), Joseph (Seffi) Naor and Niv Buchbinder (Eds.). SIAM, 2549--2579","author":"Zuzic Goran","year":"2022","unstructured":"Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, and Xiaorui Sun. 2022. Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based l1-Oblivious Routing. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), Joseph (Seffi) Naor and Niv Buchbinder (Eds.). SIAM, 2549--2579."}],"event":{"name":"SPAA '24: 36th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Nantes France","acronym":"SPAA '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626183.3659959","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626183.3659959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T16:22:58Z","timestamp":1755879778000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626183.3659959"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":67,"alternative-id":["10.1145\/3626183.3659959","10.1145\/3626183"],"URL":"https:\/\/doi.org\/10.1145\/3626183.3659959","relation":{},"subject":[],"published":{"date-parts":[[2024,6,17]]},"assertion":[{"value":"2024-06-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}