{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T14:27:14Z","timestamp":1776522434402,"version":"3.51.2"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,11,27]],"date-time":"2021-11-27T00:00:00Z","timestamp":1637971200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,27]],"date-time":"2021-11-27T00:00:00Z","timestamp":1637971200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s00446-021-00412-8","type":"journal-article","created":{"date-parts":[[2021,11,27]],"date-time":"2021-11-27T09:02:35Z","timestamp":1638003755000},"page":"357-374","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Single-source shortest paths in the CONGEST model with improved bounds"],"prefix":"10.1007","volume":"35","author":[{"given":"Shiri","family":"Chechik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Doron","family":"Mukhtar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,27]]},"reference":[{"key":"412_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, U., Ramachandran, V.: Distributed weighted all pairs shortest paths through pipelining. In: Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS \u201919), pp. 23\u201332, (2019)","DOI":"10.1109\/IPDPS.2019.00014"},{"key":"412_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, U., Ramachandran, V., King, V., Pontecorvi, M.: A deterministic distributed algorithm for exact weighted all-pairs shortest paths in $$\\tilde{O}(n^{3\/2})$$ rounds. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC \u201918), pp. 199\u2013205, (2018)","DOI":"10.1145\/3212734.3212773"},{"key":"412_CR3","unstructured":"Becker, R., Emek, Y., Ghaffari, M., Lenzen, C.: Distributed algorithms for low stretch spanning trees. In: Proceedings of the 33rd International Symposium on Distributed Computing (DISC \u201919), pp. 4:1\u20134:14, (2019)"},{"key":"412_CR4","unstructured":"Becker, R., Karrenbauer, A., Krinninger, S., Lenzen, C.: Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In: Proceedings of the 31st International Symposium on Distributed Computing (DISC \u201917), pp. 7:1\u20137:16, (2017)"},{"issue":"1","key":"412_CR5","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R Bellman","year":"1958","unstructured":"Bellman, R.: On a routing problem. Q. Appl. Math. 16(1), 87\u201390 (1958)","journal-title":"Q. Appl. Math."},{"key":"412_CR6","doi-asserted-by":"crossref","unstructured":"Bernstein, A.: Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (STOC \u201913), pp. 725\u2013734, (2013)","DOI":"10.1145\/2488608.2488701"},{"key":"412_CR7","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Nanongkai, D.: Distributed exact weighted all-pairs shortest paths in near-linear time. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201919), pp. 334\u2013342, (2019)","DOI":"10.1145\/3313276.3316326"},{"key":"412_CR8","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Dory, M., Korhonen, J.H., Leitersdorf, D.: Fast approximate shortest paths in the Congested Clique. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC \u201919), pp. 74\u201383, (2019)","DOI":"10.1145\/3293611.3331633"},{"key":"412_CR9","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the Congested Clique. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC \u201915), pp. 143\u2013152, (2015)","DOI":"10.1145\/2767386.2767414"},{"key":"412_CR10","unstructured":"Chechik, S., Mukhtar, D.: Reachability and shortest paths in the Broadcast CONGEST model. In: Proceedings of the 33rd International Symposium on Distributed Computing (DISC \u201919), pp. 11:1\u201311:13, (2019)"},{"key":"412_CR11","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 Forty-third Annual ACM Symposium on Theory of Computing (STOC \u201911), pp. 363\u2013372, (2011)","DOI":"10.1145\/1993636.1993686"},{"key":"412_CR12","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 Thirty-sixth Annual ACM Symposium on Theory of Computing (STOC \u201904), pp. 331\u2013340, (2004)","DOI":"10.1145\/1007352.1007407"},{"key":"412_CR13","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Distributed exact shortest paths in sublinear time. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC \u201917), pp. 757\u2013770, (2017)","DOI":"10.1145\/3055399.3055452"},{"key":"412_CR14","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: Hopsets with constant hopbound, and applications to approximate shortest paths. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201916), pp. 128\u2013137, (2016)","DOI":"10.1109\/FOCS.2016.22"},{"key":"412_CR15","unstructured":"Fischer, O., Oshman, R.: A distributed algorithm for directed minimum-weight spanning tree. In: Proceedings of the 33rd International Symposium on Distributed Computing (DISC \u201919), pp. 16:1\u201316:16, (2019)"},{"key":"412_CR16","unstructured":"Ford, L.R. Jr: Network flow theory. Technical Report P-923, The RAND Corporation, (1956)"},{"key":"412_CR17","doi-asserted-by":"crossref","unstructured":"Forster, S., Nanongkai, D.: A faster distributed single-source shortest paths algorithm. In: Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201918), pp. 686\u2013697, (20180","DOI":"10.1109\/FOCS.2018.00071"},{"key":"412_CR18","doi-asserted-by":"crossref","unstructured":"Friedrichs, S., Lenzen, C.: Parallel metric tree embedding based on an algebraic view on moore-bellman-ford. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA \u201916), pp. 455\u2013466, (2016)","DOI":"10.1145\/2935764.2935777"},{"key":"412_CR19","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Further algebraic algorithms in the Congested Clique model and applications to graph-theoretic problems. In: Proceedings of the 30th International Symposium on Distributed Computing (DISC \u201916), pp. 57\u201370, (2016)","DOI":"10.1007\/978-3-662-53426-7_5"},{"key":"412_CR20","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Li, J.: Improved distributed algorithms for exact shortest paths. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201918), pp. 431\u2013444, (2018)","DOI":"10.1145\/3188745.3188948"},{"key":"412_CR21","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Udwani, R.: Brief announcement: Distributed single-source reachability. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC \u201915), pp. 163\u2013165, (2015)","DOI":"10.1145\/2767386.2767444"},{"key":"412_CR22","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing (STOC \u201916), pp. 489\u2013498, (2016)","DOI":"10.1145\/2897518.2897638"},{"key":"412_CR23","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC \u201912), pp. 355\u2013364, (2012)","DOI":"10.1145\/2332432.2332504"},{"key":"412_CR24","doi-asserted-by":"crossref","unstructured":"Huang, C.-C., Nanongkai, D., Saranurak, T.: Distributed exact weighted all-pairs shortest paths in $$\\tilde{O}(n^{5\/4})$$ rounds. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201917), pp. 168\u2013179, (2017)","DOI":"10.1109\/FOCS.2017.24"},{"issue":"2","key":"412_CR25","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jagm.1997.0888","volume":"25","author":"PN Klein","year":"1997","unstructured":"Klein, P.N., Subramanian, S.: A randomized parallel algorithm for single-source shortest paths. J. Algo. 25(2), 205\u2013220 (1997)","journal-title":"J. Algo."},{"key":"412_CR26","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages. In: Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (STOC \u201913), pp. 381\u2013390, (2013)","DOI":"10.1145\/2488608.2488656"},{"key":"412_CR27","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast partial distance estimation and applications. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC \u201915), pp. 153\u2013162, (2015)","DOI":"10.1145\/2767386.2767398"},{"key":"412_CR28","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC \u201913), pp. 375\u2013382, (2013)","DOI":"10.1145\/2484239.2484262"},{"key":"412_CR29","doi-asserted-by":"crossref","unstructured":"M\u0105dry, A.: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing (STOC \u201910), pp. 121\u2013130, (2010)","DOI":"10.1145\/1806689.1806708"},{"key":"412_CR30","unstructured":"Moore, E.F.: The shortest path through a maze. In: Proceedings of an International Symposium on the Theory of Switching, Part II, pp. 285\u2013292 (1959)"},{"key":"412_CR31","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing (STOC \u201914), pp. 565\u2013573, (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"412_CR32","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"412_CR33","doi-asserted-by":"crossref","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed MST construction. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS \u201999), pp. 253\u2013261, (1999)","DOI":"10.1109\/SFFCS.1999.814597"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00412-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00412-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00412-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T04:01:54Z","timestamp":1726200114000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00412-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,27]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["412"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00412-8","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,27]]},"assertion":[{"value":"29 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}