{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:32Z","timestamp":1740109292923,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,24]],"date-time":"2020-07-24T00:00:00Z","timestamp":1595548800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,24]],"date-time":"2020-07-24T00:00:00Z","timestamp":1595548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"KAKENHI","doi-asserted-by":"crossref","award":["15H000852","16H02878"],"award-info":[{"award-number":["15H000852","16H02878"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["CCF-1527110","CCF-1618280"],"award-info":[{"award-number":["CCF-1527110","CCF-1618280"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s00446-020-00383-2","type":"journal-article","created":{"date-parts":[[2020,7,24]],"date-time":"2020-07-24T16:02:52Z","timestamp":1595606572000},"page":"79-90","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Low-Congestion shortcuts without embedding"],"prefix":"10.1007","volume":"34","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[]},{"given":"Taisuke","family":"Izumi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9322-6329","authenticated-orcid":false,"given":"Goran","family":"Zuzic","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,24]]},"reference":[{"key":"383_CR1","doi-asserted-by":"crossref","unstructured":"Das\u00a0Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 363\u2013372 (2011)","DOI":"10.1145\/1993636.1993686"},{"key":"383_CR2","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 331\u2013340 (2004)","DOI":"10.1145\/1007352.1007407"},{"issue":"2","key":"383_CR3","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36(2), 433\u2013456 (2006)","journal-title":"SIAM J. Comput."},{"key":"383_CR4","doi-asserted-by":"crossref","unstructured":"Frischknecht, Silvio., Holzer, Stephan., Wattenhofer, Roger.: Networks cannot compute their diameter in sublinear time. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"key":"383_CR5","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks I: Planar embedding. Manuscript, (2015)","DOI":"10.1145\/2933057.2933109"},{"key":"383_CR6","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Haeupler, B.: Distributed algorithms for planar networks II: Low-congestion shortcuts, mst, and min-cut. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 202\u2013219. SIAM, (2016)","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"383_CR7","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Proceedings of the International Symposium on Distributed Computing (DISC), pp. 1\u201315 (2013)","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"383_CR8","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Karrenbauer, A., Kuhn, F., Lenzen, C., Patt-Shamir, B.: Near-optimal distributed maximum flow: Extended abstract. In: The Proceedings of the International Symposim on Principles of Distributed Computing (PODC), pp. 81\u201390 (2015)","DOI":"10.1145\/2767386.2767440"},{"key":"383_CR9","unstructured":"Garay, J.A., Kutten, S.., Peleg, D.: A sub-linear time distributed algorithm for minimum-weight spanning trees. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), (1993)"},{"key":"383_CR10","unstructured":"Ghaffari, M., Li, J.: New distributed algorithms in almost mixing time via transformations from parallel algorithms. arXiv preprint arXiv:1805.04764, (2018)"},{"key":"383_CR11","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Hershkowitz, D\u00a0Ellis., Wajc, D.: Round-and message-optimal distributed graph algorithms. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pp. 119\u2013128. ACM (2018)","DOI":"10.1145\/3212734.3212737"},{"key":"383_CR12","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Izumi, T., Zuzic, G.: Low-congestion shortcuts without embedding. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 451\u2013460. ACM (2016)","DOI":"10.1145\/2933057.2933112"},{"key":"383_CR13","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Izumi, T., Zuzic, G.: Near-optimal low-congestion shortcuts on bounded parameter graphs. In: International Symposium on Distributed Computing, pp. 158\u2013172. Springer (2016)","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"383_CR14","unstructured":"Haeupler, B., Li, J.: Faster distributed shortest path approximations via shortcuts. arXiv preprint arXiv:1802.03671 (2018)"},{"key":"383_CR15","doi-asserted-by":"crossref","unstructured":"Haeupler,B., Li, J., Zuzic, G.: Minor excluded network families admit fast distributed algorithms. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pp. 465\u2013474. ACM (2018)","DOI":"10.1145\/3212734.3212776"},{"key":"383_CR16","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: The Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp. 355\u2013364 (2012)","DOI":"10.1145\/2332432.2332504"},{"key":"383_CR17","doi-asserted-by":"crossref","unstructured":"Izumi, T., Wattenhofer, R.: Time lower bounds for distributed distance oracles. In: Proceedings of the International Conference on Principles of Distributed Systems, pp. 60\u201375 (2014)","DOI":"10.1007\/978-3-319-14472-6_5"},{"key":"383_CR18","doi-asserted-by":"crossref","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pp 238\u2013251 (1995)","DOI":"10.1145\/224964.224990"},{"issue":"6","key":"383_CR19","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00446-007-0047-8","volume":"20","author":"M Khan","year":"2008","unstructured":"Khan, M., Pandurangan, G.: A fast distributed approximation algorithm for minimum spanning trees. Distrib. Comput. 20(6), 391\u2013402 (2008)","journal-title":"Distrib. Comput."},{"issue":"2","key":"383_CR20","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"L Frank\u00a0Thomson","year":"1994","unstructured":"Frank\u00a0Thomson, L., Bruce\u00a0M, M., Satish\u00a0B, R.: Packet routing and job-shop scheduling in O(congestion+ dilation) steps. Combinatorica 14(2), 167\u2013186 (1994)","journal-title":"Combinatorica"},{"issue":"2","key":"383_CR21","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00446-018-0326-6","volume":"32","author":"C Lenzen","year":"2019","unstructured":"Lenzen, C., Patt-Shamir, B., Peleg, D.: Distributed distance computation and routing with small messages. Distrib. Comput. 32(2), 133\u2013157 (2019)","journal-title":"Distrib. Comput."},{"key":"383_CR22","doi-asserted-by":"crossref","unstructured":"Nnongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 565\u2013573 (2014)","DOI":"10.1145\/2591796.2591850"},{"issue":"1","key":"383_CR23","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0012-365X(00)00224-7","volume":"233","author":"J Ne\u0161et\u0159il","year":"2001","unstructured":"Ne\u0161et\u0159il, J., Milkov\u00e1, E., Ne\u0161et\u0159ilov\u00e1, H.: Otakar boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Math. 233(1), 3\u201336 (2001)","journal-title":"Discrete Math."},{"key":"383_CR24","doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Su, H.-H.: Almost-tight distributed minimum cut algorithms. In: Proceedings of the International Symposium on Distributed Computing (DISC), pp 439\u2013453 (2014)","DOI":"10.1007\/978-3-662-45174-8_30"},{"key":"383_CR25","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"383_CR26","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed MST construction. In: Proceedings of the Symposium on Foundation of Computer Science (FOCS), p 253 (1999)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00383-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00383-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00383-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T23:43:48Z","timestamp":1627083828000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00383-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,24]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["383"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00383-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2020,7,24]]},"assertion":[{"value":"11 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}