{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T11:03:15Z","timestamp":1762254195014,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program","award":["853109"],"award-info":[{"award-number":["853109"]}]},{"name":"Swiss National Foundation","award":["200021-184735"],"award-info":[{"award-number":["200021-184735"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538429","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"281-291","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Universally-Optimal Distributed Exact Min-Cut"],"prefix":"10.1145","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[{"name":"MIT, Cambridge, MA, USA"}]},{"given":"Goran","family":"Zuzic","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Minimum Cuts in Directed Graphs via Partial Sparsification. arXiv preprint arXiv:2111.08959","author":"Cen Ruoxu","year":"2021","unstructured":"Ruoxu Cen , Jason Li , Danupon Nanongkai , Debmalya Panigrahi , Kent Quanrud , and Thatchaphol Saranurak . 2021. Minimum Cuts in Directed Graphs via Partial Sparsification. arXiv preprint arXiv:2111.08959 ( 2021 ). Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud, and Thatchaphol Saranurak. 2021. Minimum Cuts in Directed Graphs via Partial Sparsification. arXiv preprint arXiv:2111.08959 (2021)."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316346"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451020"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331617"},{"key":"e_1_3_2_2_7_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"15","author":"Gawrychowski Pawel","year":"2020","unstructured":"Pawel Gawrychowski , Shay Mozes , and Oren Weimann . 2020 . Minimum Cut in O(m log2 n) Time . In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 168), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 57:1--57: 15 . https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.57 10.4230\/LIPIcs.ICALP.2020.57 Pawel Gawrychowski, Shay Mozes, and Oren Weimann. 2020. Minimum Cut in O(m log2 n) Time. In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 168), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 57:1--57:15. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.57"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.8"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884451"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467935"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087827"},{"key":"e_1_3_2_2_13_1","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC). 31:1--31:16","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Jason Li . 2018 . New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms . In Proceedings of the 32nd International Symposium on Distributed Computing (DISC). 31:1--31:16 . Mohsen Ghaffari and Jason Li. 2018. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC). 31:1--31:16."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.77"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933103"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212737"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933112"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212776"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520026"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451081"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/331605.331608"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451114"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461806"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384334"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_30"},{"key":"e_1_3_2_2_27_1","volume-title":"Some simple distributed algorithms for sparse networks. Distributed computing 14, 2","author":"Panconesi Alessandro","year":"2001","unstructured":"Alessandro Panconesi and Romeo Rizzi . 2001. Some simple distributed algorithms for sparse networks. Distributed computing 14, 2 ( 2001 ), 97--100. Alessandro Panconesi and Romeo Rizzi. 2001. Some simple distributed algorithms for sparse networks. Distributed computing 14, 2 (2001), 97--100."},{"key":"e_1_3_2_2_28_1","volume-title":"Small Cuts and Connectivity Certificates: A Fault Tolerant Approach. In 33rd International Symposium on Distributed Computing.","author":"Parter Merav","year":"2019","unstructured":"Merav Parter . 2019 . Small Cuts and Connectivity Certificates: A Fault Tolerant Approach. In 33rd International Symposium on Distributed Computing. Merav Parter. 2019. Small Cuts and Connectivity Certificates: A Fault Tolerant Approach. In 33rd International Symposium on Distributed Computing."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.  David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_2_30_1","volume-title":"Annual ACM Symposium on Theory of Computing (STOC)","author":"Rozhoc V\u00e1clav","year":"2022","unstructured":"V\u00e1clav Rozhoc , Christoph Grunau , Bernhard Haeupler , Goran Zuzic , and Jason Li . 2022 . Undirected (1+epsilon)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms . Annual ACM Symposium on Theory of Computing (STOC) (2022). V\u00e1clav Rozhoc, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, and Jason Li. 2022. Undirected (1+epsilon)-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms. Annual ACM Symposium on Theory of Computing (STOC) (2022)."},{"key":"e_1_3_2_2_31_1","volume-title":"Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM.","author":"Zuzic Goran","year":"2022","unstructured":"Goran Zuzic , Goramoz 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 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. Goran Zuzic, Goramoz 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 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM."}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Salerno Italy","acronym":"PODC '22"},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538429","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":31,"alternative-id":["10.1145\/3519270.3538429","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538429","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}