{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:27Z","timestamp":1740109287867,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["724\/15","1817\/17"],"award-info":[{"award-number":["724\/15","1817\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2015813"],"award-info":[{"award-number":["2015813"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00446-022-00431-z","type":"journal-article","created":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T12:03:24Z","timestamp":1656504204000},"page":"419-437","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC"],"prefix":"10.1007","volume":"35","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4179-4364","authenticated-orcid":false,"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,29]]},"reference":[{"key":"431_CR1","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear cost sequential and distribured constructions of sparse neighborhood covers. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5, 638\u2013647, (1993)"},{"key":"431_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Bodwin, G., Pettie, S.: A hierarchy of lower bounds for sublinear additive spanners. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, 568\u2013576, (2017)","DOI":"10.1137\/1.9781611974782.36"},{"key":"431_CR3","doi-asserted-by":"crossref","unstructured":"Andoni, A., Stein, C., Zhong, P.: Parallel approximate undirected shortest paths via low hop emulators. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC, 322-335, New York, NY, USA, (2020). Association for Computing Machinery","DOI":"10.1145\/3357713.3384321"},{"key":"431_CR4","doi-asserted-by":"crossref","unstructured":"Bernstein, A: Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, Atlanta, Georgia, USA, 693\u2013702, (2009)","DOI":"10.1109\/FOCS.2009.16"},{"key":"431_CR5","unstructured":"Becker, R., Karrenbauer, A., Krinninger, S., Lenzen, C.: Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In 31st International Symposium on Distributed Computing, DISC, October 16-20, Vienna, Austria, pages 7:1\u20137:16, (2017)"},{"key":"431_CR6","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Dory, M., Korhonen, J.H., Leitersdorf, D.: Fast approximate shortest paths in the congested clique. In Robinson, P., Ellen, F. (eds), Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 74\u201383. ACM, (2019)","DOI":"10.1145\/3293611.3331633"},{"key":"431_CR7","unstructured":"Chaudhuri, P.: Parallel algorithms - designs and analysis. Advances in computer science series. Prentice Hall, (1992)"},{"key":"431_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Madry, A., Sankowski, P., Vladu, A.: Negative-weight shortest paths and unit capacity minimum cost flow in \u00f5 (m$${}^{\\text{10\/7}}$$ log W) time (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 752\u2013771, (2017)","DOI":"10.1137\/1.9781611974782.48"},{"key":"431_CR9","unstructured":"Cohen, E: Fast algorithms for constructing t-spanners and paths with stretch t. In 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, pages 648\u2013658, (1993)"},{"issue":"1","key":"431_CR10","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1006\/jagm.1996.0813","volume":"22","author":"E Cohen","year":"1997","unstructured":"Cohen, E.: Using selective path-doubling for parallel shortest-path computations. J. Algorithms 22(1), 30\u201356 (1997)","journal-title":"J. Algorithms"},{"issue":"1","key":"431_CR11","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/331605.331610","volume":"47","author":"E Cohen","year":"2000","unstructured":"Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM 47(1), 132\u2013166 (2000)","journal-title":"J. ACM"},{"key":"431_CR12","doi-asserted-by":"crossref","unstructured":"Dory, M., Parter, M.: Exponentially faster shortest paths in the congested clique. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC 20, page 59-68, New York, NY, USA, (2020). Association for Computing Machinery","DOI":"10.1145\/3382734.3405711"},{"key":"431_CR13","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Computing almost shortest paths. In Proc. 20th ACM Symp. on Principles of Distributed Computing, 53\u201362, (2001)","DOI":"10.1145\/383962.383983"},{"key":"431_CR14","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 2017, pages 757\u2013770, New York, NY, USA, (2017). ACM","DOI":"10.1145\/3055399.3055452"},{"key":"431_CR15","doi-asserted-by":"crossref","unstructured":"Elkin, M., Matar, S.: Deterministic pram approximate shortest paths in polylogarithmic time and near-linear work. (2020). manuscript","DOI":"10.1145\/3409964.3461809"},{"key":"431_CR16","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: On efficient distributed construction of near optimal routing schemes: Extended abstract. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC \u201916, pages 235\u2013244, New York, NY, USA, (2016). ACM","DOI":"10.1145\/2933057.2933098"},{"key":"431_CR17","unstructured":"Elkin, M., Neiman, O.: Linear-size hopsets with small hopbound, and distributed routing with low memory. CoRR, arXiv:1704.08468, (2017)"},{"key":"431_CR18","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: Near-optimal distributed routing with low memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 207\u2013216 (2018)","DOI":"10.1145\/3212734.3212761"},{"issue":"4","key":"431_CR19","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1137\/18M1166791","volume":"48","author":"M Elkin","year":"2019","unstructured":"Elkin, M., Neiman, O.: Hopsets with constant hopbound, and applications to approximate shortest paths. SIAM J. Comput. 48(4), 1436\u20131480 (2019)","journal-title":"SIAM J. Comput."},{"key":"431_CR20","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC. In The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019., pages 333\u2013341, (2019)","DOI":"10.1145\/3323165.3323177"},{"issue":"3","key":"431_CR21","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: (1+epsilon, beta)-spanner constructions for general graphs. SIAM J. Comput. 33(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"431_CR22","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00446-005-0147-2","volume":"18","author":"M Elkin","year":"2006","unstructured":"Elkin, M., Zhang, J.: Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models. Distributed Computing 18(5), 375\u2013385 (2006)","journal-title":"Distributed Computing"},{"key":"431_CR23","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, pages 455\u2013466, New York, NY, USA, (2016). ACM","DOI":"10.1145\/2935764.2935777"},{"key":"431_CR24","unstructured":"Gupta, S., Kosowski, A., Viennot, L: Exploiting hopsets: Improved distance oracles for graphs of constant highway dimension and beyond. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 143:1\u2013143:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019)"},{"issue":"1","key":"431_CR25","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y Han","year":"2004","unstructured":"Han, Y.: Deterministic sorting in o(nloglogn) time and linear space. J. Algorithms 50(1), 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"key":"431_CR26","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: Decremental single-source shortest paths on undirected graphs in near-linear total update time. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 146\u2013155, (2014)","DOI":"10.1109\/FOCS.2014.24"},{"key":"431_CR27","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, pages 489\u2013498, New York, NY, USA, (2016). ACM","DOI":"10.1145\/2897518.2897638"},{"key":"431_CR28","first-page":"04","volume":"142","author":"S-E Huang","year":"2017","unstructured":"Huang, S.-E., Pettie, S.: Thorup-zwick emulators are universally optimal hopsets. Information Processing Letters 142, 04 (2017)","journal-title":"Information Processing Letters"},{"key":"431_CR29","unstructured":"Han, Y., Thorup, M.: Integer sorting in 0(n sqrt (log log n)) expected time and linear space. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 135\u2013144, (2002)"},{"issue":"2","key":"431_CR30","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. Algorithms 25(2), 205\u2013220 (1997)","journal-title":"J. Algorithms"},{"key":"431_CR31","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0020-0190(82)90093-X","volume":"14","author":"L Kucera","year":"1981","unstructured":"Kucera, L.: Parallel computation and conflicts in memory access. Inform. Process. Lett. 14, 93\u201396 (1981)","journal-title":"Inform. Process. Lett."},{"key":"431_CR32","doi-asserted-by":"crossref","unstructured":"Li, J.: Faster parallel algorithm for approximate shortest path. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 308-321, New York, NY, USA, (2020). Association for Computing Machinery","DOI":"10.1145\/3357713.3384268"},{"issue":"2","key":"431_CR33","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"FT Leighton","year":"1994","unstructured":"Leighton, F.T., Maggs, B.M., Rao, S.: Packet routing and job-shop scheduling in (congestion + dilation) steps. Combinatorica 14(2), 167\u2013186 (1994)","journal-title":"Combinatorica"},{"key":"431_CR34","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 2015, Donostia-San Sebasti\u00e1n, Spain, July 21 - 23, 2015, pages 153\u2013162, (2015)","DOI":"10.1145\/2767386.2767398"},{"key":"431_CR35","unstructured":"Lenzen, C., Patt-Shamir, B., Peleg, D.: Distributed distance computation and routing with small messages, (2016). manuscript"},{"key":"431_CR36","doi-asserted-by":"crossref","unstructured":"Madry, A.: Computing maximum flow with augmenting electrical flows. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October, Hyatt Regency, New Brunswick, New Jersey, USA, pages 593\u2013602, (2016)","DOI":"10.1109\/FOCS.2016.70"},{"key":"431_CR37","doi-asserted-by":"crossref","unstructured":"Miller, G.L., Peng, R., Vladu, A., Xu, S.C.: Improved parallel algorithms for spanners and hopsets. In Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201915, pages 192\u2013201, New York, NY, USA, (2015). ACM","DOI":"10.1145\/2755573.2755574"},{"key":"431_CR38","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Symposium on Theory of Computing, STOC, New York, NY, USA, May 31 - June 03, 565\u2013573, (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"431_CR39","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in o(nm) time, or better. In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1-4, 2013, pages 765\u2013774, (2013)","DOI":"10.1145\/2488608.2488705"},{"issue":"1","key":"431_CR40","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1006\/jagm.1998.0968","volume":"30","author":"H Shi","year":"1999","unstructured":"Shi, H., Spencer, T.H.: Time-work tradeoffs of the single-source shortest paths problem. J. Algorithms 30(1), 19\u201332 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"431_CR41","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y Shiloach","year":"1981","unstructured":"Shiloach, Y., Vishkin, U.: Finding the maximum, merging, and sorting in a parallel computation model. J. Algorithms 2(1), 88\u2013102 (1981)","journal-title":"J. Algorithms"},{"key":"431_CR42","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In Proc. of the 33rd ACM Symp. on Theory of Computing, 183\u2013192, (2001)","DOI":"10.1145\/380752.380798"},{"key":"431_CR43","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In Proc. of Symp. on Discr. Algorithms, 802\u2013809, (2006)","DOI":"10.1145\/1109557.1109645"},{"issue":"1","key":"431_CR44","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1137\/0220006","volume":"20","author":"JD Ullman","year":"1991","unstructured":"Ullman, J.D., Yannakakis, M.: High-probability parallel transitive-closure algorithms. SIAM J. Comput. 20(1), 100\u2013125 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00431-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-022-00431-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00431-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,9]],"date-time":"2022-09-09T07:13:01Z","timestamp":1662707581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-022-00431-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,29]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["431"],"URL":"https:\/\/doi.org\/10.1007\/s00446-022-00431-z","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2022,6,29]]},"assertion":[{"value":"7 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}