{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:53:54Z","timestamp":1780073634703,"version":"3.54.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","funder":[{"name":"Israel Science Foundation (ISF)","award":["810\/21"],"award-info":[{"award-number":["810\/21"]}]},{"name":"European Research Council (ERC)","award":["949083"],"award-info":[{"award-number":["949083"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733521","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"278-286","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Distributed Maximum Flow in Planar Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-5450-9910","authenticated-orcid":false,"given":"Yaseen","family":"Abd-Elhaleem","sequence":"first","affiliation":[{"name":"University of Haifa, Haifa, Israel"}],"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-0002-2357-2445","authenticated-orcid":false,"given":"Merav","family":"Parter","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4510-7552","authenticated-orcid":false,"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[{"name":"University of Haifa, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Maximilian Probst Gutenberg, and Sushant Sachdeva","author":"Chen Li","year":"2022","unstructured":"Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2022. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. In 63rd FOCS. 612\u2013623."},{"key":"e_1_3_2_1_2_1","volume-title":"30th SIROCCO. 406\u2013426.","author":"de Vos Tijn","unstructured":"Tijn de Vos. 2023. Minimum Cost Flow in the CONGEST Model. In 30th SIROCCO. 406\u2013426."},{"key":"e_1_3_2_1_3_1","volume-title":"53rd STOC. 1144\u20131153.","author":"Dory Michal","unstructured":"Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. 2021. Distributed weighted min-cut in nearly-optimal time. In 53rd STOC. 1144\u20131153."},{"key":"e_1_3_2_1_4_1","volume-title":"Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs. In 41tst PODC. 67\u201370.","author":"Dou Jinfeng","year":"2023","unstructured":"Jinfeng Dou, Thorsten G\u00f6tte, Henning Hillebrandt, Christian Scheideler, and Julian Werthmann. 2023. Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs. In 41tst PODC. 67\u201370."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_2_1_6_1","volume-title":"23rd SODA. 1150\u20131162.","author":"Frischknecht Silvio","unstructured":"Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. 2012. Networks cannot compute their diameter in sublinear time. In 23rd SODA. 1150\u20131162."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261118"},{"key":"e_1_3_2_1_8_1","volume-title":"12th SODA. 210\u2013219.","author":"Gavoille Cyril","unstructured":"Cyril Gavoille, David Peleg, St\u00e9phane P\u00e9rennes, and Ran Raz. 2001. Distance Labeling in Graphs. In 12th SODA. 210\u2013219."},{"key":"e_1_3_2_1_9_1","volume-title":"34th PODC. 29\u201338.","author":"Ghaffari Mohsen","unstructured":"Mohsen Ghaffari and Bernhard Haeupler. 2016. Distributed Algorithms for Planar Networks I: Planar Embedding. In 34th PODC. 29\u201338."},{"key":"e_1_3_2_1_10_1","volume-title":"MST, and Min-Cut. In 27th SODA. 202\u2013219.","author":"Ghaffari Mohsen","unstructured":"Mohsen Ghaffari and Bernhard Haeupler. 2016. Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. In 27th SODA. 202\u2013219."},{"key":"e_1_3_2_1_11_1","volume-title":"33rd PODC. 81\u201390.","author":"Ghaffari Mohsen","unstructured":"Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir. 2015. Near-optimal distributed maximum flow. In 33rd PODC. 81\u201390."},{"key":"e_1_3_2_1_12_1","volume-title":"31st DISC. 21:1\u201321:16.","author":"Ghaffari Mohsen","unstructured":"Mohsen Ghaffari and Merav Parter. 2017. Near-Optimal Distributed DFS in Planar Graphs. In 31st DISC. 21:1\u201321:16."},{"key":"e_1_3_2_1_13_1","volume-title":"40th PODC. 281\u2013291.","author":"Ghaffari Mohsen","unstructured":"Mohsen Ghaffari and Goran Zuzic. 2022. Universally-Optimal Distributed Exact Min-Cut. In 40th PODC. 281\u2013291."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90120-4"},{"key":"e_1_3_2_1_15_1","volume-title":"30th PODC. 355\u2013364.","author":"Holzer Stephan","unstructured":"Stephan Holzer and Roger Wattenhofer. 2012. Optimal distributed all pairs shortest paths and applications. In 30th PODC. 355\u2013364."},{"key":"e_1_3_2_1_16_1","volume-title":"A nearly optimal distributed algorithm for computing the weighted girth. Sci. China Inf. Sci. 64, 11","author":"Hua Qiang-Sheng","year":"2021","unstructured":"Qiang-Sheng Hua, Lixiang Qian, Dongxiao Yu, Xuanhua Shi, and Hai Jin. 2021. A nearly optimal distributed algorithm for computing the weighted girth. Sci. China Inf. Sci. 64, 11 (2021)."},{"key":"e_1_3_2_1_17_1","volume-title":"51st STOC. 152\u2013163.","author":"Li Jason","unstructured":"Jason Li and Merav Parter. 2019. Planar diameter via metric compression. In 51st STOC. 152\u2013163."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_1_19_1","volume-title":"43rd PODC. 182\u2013193.","author":"Manoharan Vignesh","unstructured":"Vignesh Manoharan and Vijaya Ramachandran. 2024. Computing Minimum Weight Cycle in the CONGEST Model. In 43rd PODC. 182\u2013193."},{"key":"e_1_3_2_1_20_1","volume-title":"16th STOC. 376\u2013382.","author":"Miller Gary L.","unstructured":"Gary L. Miller. 1984. Finding Small Simple Cycle Separators for 2-Connected Planar Graphs.. In 16th STOC. 376\u2013382."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539789162997"},{"key":"e_1_3_2_1_22_1","volume-title":"46th STOC. 565\u2013573.","author":"Nanongkai Danupon","unstructured":"Danupon Nanongkai. 2014. Distributed approximation algorithms for weighted shortest paths. In 46th STOC. 565\u2013573."},{"key":"e_1_3_2_1_23_1","volume-title":"33rd DISC. 30:1\u201330:16.","author":"Parter Merav","unstructured":"Merav Parter. 2019. Small Cuts and Connectivity Certificates: A Fault Tolerant Approach. In 33rd DISC. 30:1\u201330:16."},{"key":"e_1_3_2_1_24_1","volume-title":"34th DISC","volume":"179","author":"Parter Merav","year":"2020","unstructured":"Merav Parter. 2020. Distributed Planar Reachability in Nearly Optimal Time. In 34th DISC, Vol. 179. 38:1\u201338:17."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_26_1","volume-title":"39th ICALP. 660\u2013672.","author":"Peleg David","unstructured":"David Peleg, Liam Roditty, and Elad Tal. 2012. Distributed Algorithms for Network Diameter and Girth. In 39th ICALP. 660\u2013672."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212005"},{"key":"e_1_3_2_1_28_1","volume-title":"43rd STOC. 363\u2013372.","author":"Sarma Atish Das","unstructured":"Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. 2011. Distributed verification and hardness of distributed approximation. In 43rd STOC. 363\u2013372."},{"key":"e_1_3_2_1_29_1","volume-title":"55th STOC. 321\u2013334.","author":"Rozhon V\u00e1clav","unstructured":"V\u00e1clav Rozhon, Bernhard Haeupler, Anders Martinsson, Christoph Grunau, Goran Zuzic. 2023. Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances. In 55th STOC. 321\u2013334."},{"key":"e_1_3_2_1_30_1","volume-title":"54th STOC. 478\u2013487.","author":"Rozhon V\u00e1clav","unstructured":"V\u00e1clav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li. 2022. Undirected (1+\u03f5)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithms. In 54th STOC. 478\u2013487."},{"key":"e_1_3_2_1_31_1","volume-title":"33rd SODA. 2549\u20132579.","author":"Zuzic Goran","unstructured":"Goran Zuzic, Gramoz Goranci, Mingquan Ye, Bernhard Haeupler, Xiaorui Sun. 2022. Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based l1-Oblivious Routing. In 33rd SODA. 2549\u20132579."}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732772.3733521","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:24:06Z","timestamp":1749824646000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733521"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":31,"alternative-id":["10.1145\/3732772.3733521","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733521","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}