{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:46:40Z","timestamp":1773704800101,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, CCF-1750808"],"award-info":[{"award-number":["CCF-1527110, CCF-1618280, CCF-1814603, CCF-1910588, CCF-1750808"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swiss National Science Foundation","award":["200021-184735"],"award-info":[{"award-number":["200021-184735"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["853109, 949272"],"award-info":[{"award-number":["853109, 949272"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467935","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"213-221","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Low-Congestion Shortcuts for Graphs Excluding Dense Minors"],"prefix":"10.1145","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University & ETH Z\u00fcrich, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331617"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007407"},{"key":"e_1_3_2_2_4_1","volume-title":"Proc. of the Symp. on Found. of Comp. Sci. (FOCS).","author":"Garay J.A.","unstructured":"J.A. Garay , S. Kutten , and D. Peleg . 1993. A sub-linear time distributed algorithm for minimum-weight spanning trees . In Proc. of the Symp. on Found. of Comp. Sci. (FOCS). J.A. Garay, S. Kutten, and D. Peleg. 1993. A sub-linear time distributed algorithm for minimum-weight spanning trees. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS)."},{"key":"e_1_3_2_2_5_1","volume-title":"Near-Optimal Scheduling of Distributed Algorithms. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC).","author":"Ghaffari Mohsen","year":"2015","unstructured":"Mohsen Ghaffari . 2015 . Near-Optimal Scheduling of Distributed Algorithms. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC). to appear. Mohsen Ghaffari. 2015. Near-Optimal Scheduling of Distributed Algorithms. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC). to appear."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933109"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087827"},{"key":"e_1_3_2_2_9_1","volume-title":"32nd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","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 32nd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Mohsen Ghaffari and Jason Li. 2018. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In 32nd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_10_1","volume-title":"31st International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari and Merav Parter . 2017 . Near-optimal distributed DFS in planar graphs . In 31st International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Mohsen Ghaffari and Merav Parter. 2017. Near-optimal distributed DFS in planar graphs. In 31st International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212737"},{"key":"e_1_3_2_2_13_1","volume-title":"Near-Optimal Schedules for Simultaneous Multicasts. arXiv cs.DS","author":"Haeupler Bernhard","year":"2001","unstructured":"Bernhard Haeupler , D Ellis Hershkowitz , and David Wajc . 2019. Near-Optimal Schedules for Simultaneous Multicasts. arXiv cs.DS 2001 .00072 (2019). Bernhard Haeupler, D Ellis Hershkowitz, and David Wajc. 2019. Near-Optimal Schedules for Simultaneous Multicasts. arXiv cs.DS 2001.00072 (2019)."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933112"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"e_1_3_2_2_16_1","volume-title":"32nd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Haeupler Bernhard","year":"2018","unstructured":"Bernhard Haeupler and Jason Li . 2018 . Faster Distributed Shortest Path Approximations via Shortcuts . In 32nd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Bernhard Haeupler and Jason Li. 2018. Faster Distributed Shortest Path Approximations via Shortcuts. In 32nd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212776"},{"key":"e_1_3_2_2_18_1","volume-title":"Low-Congestion Shortcut and Graph Parameters. In 33rd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Kitamura Naoki","year":"2019","unstructured":"Naoki Kitamura , Hirotaka Kitagawa , Yota Otachi , and Taisuke Izumi . 2019 . Low-Congestion Shortcut and Graph Parameters. In 33rd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, and Taisuke Izumi. 2019. Low-Congestion Shortcut and Graph Parameters. In 33rd International Symposium on Distributed Computing (DISC). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_19_1","volume-title":"Fast Distributed Construction of K-dominating Sets and Applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC). 238--251","author":"Kutten Shay","year":"1995","unstructured":"Shay Kutten and David Peleg . 1995 . Fast Distributed Construction of K-dominating Sets and Applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC). 238--251 . Shay Kutten and David Peleg. 1995. Fast Distributed Construction of K-dominating Sets and Applications. In the Proc. of the Int'l Symp. on Princ. of Dist. Comp. (PODC). 238--251."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316358"},{"key":"e_1_3_2_2_22_1","volume-title":"Problems, and Proofs: Essays from G\u00f6del's Lost Letter: 2010","author":"Lipton Richard J","unstructured":"Richard J Lipton and Kenneth W Regan . 2013. People , Problems, and Proofs: Essays from G\u00f6del's Lost Letter: 2010 . Springer Science & Business Media . Richard J Lipton and Kenneth W Regan. 2013. People, Problems, and Proofs: Essays from G\u00f6del's Lost Letter: 2010 .Springer Science & Business Media."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"e_1_3_2_2_24_1","volume-title":"Treewidth, Kernels, and Algorithms","author":"Lokshtanov Daniel","unstructured":"Daniel Lokshtanov , Saket Saurabh , and Meirav Zehavi . 2020. Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths . In Treewidth, Kernels, and Algorithms . Springer , 112--128. Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. 2020. Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths. In Treewidth, Kernels, and Algorithms. Springer, 112--128."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0127-6"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808703"},{"key":"e_1_3_2_2_27_1","volume-title":"Sparsity: graphs, structures, and algorithms","author":"Patrice Ossona De Mendez Jaroslav Nevs","unstructured":"Jaroslav Nevs etvr il and Patrice Ossona De Mendez . 2012. Sparsity: graphs, structures, and algorithms . Vol. 28 . Springer Science & Business Media . Jaroslav Nevs etvr il and Patrice Ossona De Mendez. 2012. Sparsity: graphs, structures, and algorithms. Vol. 28. Springer Science & Business Media."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00224-7"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814597"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","location":"Virtual Event Italy","acronym":"PODC '21","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467935","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467935","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467935","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467935"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":34,"alternative-id":["10.1145\/3465084.3467935","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467935","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}