{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T06:18:07Z","timestamp":1790662687567,"version":"4.1.0"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T00:00:00Z","timestamp":1590624000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T00:00:00Z","timestamp":1590624000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Institute of Science and Technology"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We design fast <jats:italic>deterministic<\/jats:italic> algorithms for distance computation in the <jats:sc>Congested Clique<\/jats:sc> model. Our key contributions include:<jats:list list-type=\"bullet\">\n                <jats:list-item>\n                  <jats:p>A <jats:inline-formula><jats:alternatives><jats:tex-math>$$(2+\\epsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mi>\u03f5<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for all-pairs shortest paths in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\log ^2{n} \/ \\epsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:msup>\n                          <mml:mo>log<\/mml:mo>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mi>\u03f5<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first <jats:italic>sub-polynomial<\/jats:italic> constant-factor approximation for APSP in this model.<\/jats:p>\n                <\/jats:list-item>\n                <jats:list-item>\n                  <jats:p>A <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1+\\epsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mi>\u03f5<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for multi-source shortest paths from <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:msqrt>\n                          <mml:mi>n<\/mml:mi>\n                        <\/mml:msqrt>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> sources in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\log ^2{n} \/ \\epsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>O<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:msup>\n                          <mml:mo>log<\/mml:mo>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mi>\u03f5<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds on weighted undirected graphs. This is the first <jats:italic>sub-polynomial<\/jats:italic> algorithm obtaining this approximation for a set of sources of polynomial size.<\/jats:p>\n                <\/jats:list-item>\n              <\/jats:list> Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an <jats:italic>exact<\/jats:italic> single-source shortest paths algorithm for weighted undirected graphs in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\tilde{O}(n^{1\/6})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mover>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>~<\/mml:mo>\n                    <\/mml:mover>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mn>1<\/mml:mn>\n                          <mml:mo>\/<\/mml:mo>\n                          <mml:mn>6<\/mml:mn>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds.\n<\/jats:p>","DOI":"10.1007\/s00446-020-00380-5","type":"journal-article","created":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T06:02:26Z","timestamp":1590645746000},"page":"463-487","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Fast approximate shortest paths in the congested clique"],"prefix":"10.1007","volume":"34","author":[{"given":"Keren","family":"Censor-Hillel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Dory","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Janne H.","family":"Korhonen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dean","family":"Leitersdorf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,5,28]]},"reference":[{"issue":"6","key":"380_CR1","doi-asserted-by":"publisher","first-page":"2203","DOI":"10.1137\/16M1105815","volume":"47","author":"A Abboud","year":"2018","unstructured":"Abboud, A., Bodwin, G., Pettie, S.: A hierarchy of lower bounds for sublinear additive spanners. SIAM J. Comput. 47(6), 2203\u20132236 (2018)","journal-title":"SIAM J. Comput."},{"key":"380_CR2","first-page":"29","volume":"2016","author":"A Abboud","year":"2016","unstructured":"Abboud, A., Censor-Hillel, K., Khoury, S.: Near-linear lower bounds for distributed distance computations, even in sparse networks. Proc. DISC 2016, 29\u201342 (2016)","journal-title":"Proc. DISC"},{"key":"380_CR3","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1145\/3212734.3212773","volume":"2018","author":"U Agarwal","year":"2018","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. Proc. PODC 2018, 199\u2013205 (2018). https:\/\/doi.org\/10.1145\/3212734.3212773","journal-title":"Proc. PODC"},{"issue":"4","key":"380_CR4","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"380_CR5","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/3188745.3188950","volume":"2018","author":"A Backurs","year":"2018","unstructured":"Backurs, A., Roditty, L., Segal, G., Williams, V.V., Wein, N.: Towards tight approximation bounds for graph diameter and eccentricities. Proc. STOC 2018, 267\u2013280 (2018). https:\/\/doi.org\/10.1145\/3188745.3188950","journal-title":"Proc. STOC"},{"key":"380_CR6","first-page":"666","volume":"2005","author":"S Baswana","year":"2005","unstructured":"Baswana, S., Goyal, V., Sen, S.: All-pairs nearly 2-approximate shortest-paths in $${O}(n^2\\operatorname{polylog}n)$$ time. Proc. STACS 2005, 666\u2013679 (2005)","journal-title":"Proc. STACS"},{"issue":"7","key":"380_CR7","doi-asserted-by":"publisher","first-page":"2865","DOI":"10.1137\/080737174","volume":"39","author":"S Baswana","year":"2010","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM J. Comput. 39(7), 2865\u20132896 (2010)","journal-title":"SIAM J. Comput."},{"key":"380_CR8","doi-asserted-by":"publisher","unstructured":"Becker, R., Karrenbauer, A., Krinninger, S., Lenzen, C.: Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In: Proc. DISC 2017 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.7","DOI":"10.4230\/LIPIcs.DISC.2017.7"},{"issue":"1","key":"380_CR9","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":"380_CR10","first-page":"541","volume":"2007","author":"P Berman","year":"2007","unstructured":"Berman, P., Kasiviswanathan, S.P.: Faster approximation of distances in graphs. Proc. WADS 2007, 541\u2013552 (2007)","journal-title":"Proc. WADS"},{"key":"380_CR11","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1109\/FOCS.2009.16","volume":"2009","author":"A Bernstein","year":"2009","unstructured":"Bernstein, A.: Fully dynamic $$(2 + \\epsilon )$$-approximate all-pairs shortest paths with fast query and close to linear update time. Proc. FOCS 2009, 693\u2013702 (2009). https:\/\/doi.org\/10.1109\/FOCS.2009.16","journal-title":"Proc. FOCS"},{"key":"380_CR12","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Nanongkai, D.: Distributed exact weighted all-pairs shortest paths in near-linear time (2018). ArXiv:1811.03337 [cs.DC]","DOI":"10.1145\/3313276.3316326"},{"key":"380_CR13","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: Proc. PODC 2015, pp. 143\u2013152. ACM (2015)","DOI":"10.1145\/2767386.2767414"},{"key":"380_CR14","doi-asserted-by":"publisher","unstructured":"Censor-Hillel, K., Leitersdorf, D., Turner, E.: Sparse matrix multiplication and triangle listing in the congested clique model. In: Proc. OPODIS 2018 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2018.4","DOI":"10.4230\/LIPIcs.OPODIS.2018.4"},{"key":"380_CR15","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1137\/1.9781611975482.51","volume":"2018","author":"YJ Chang","year":"2018","unstructured":"Chang, Y.J., Pettie, S., Zhang, H.: Distributed triangle detection via expander decomposition. Proc. SODA 2018, 821\u2013840 (2018). https:\/\/doi.org\/10.1137\/1.9781611975482.51","journal-title":"Proc. SODA"},{"key":"380_CR16","first-page":"1041","volume":"2014","author":"S Chechik","year":"2014","unstructured":"Chechik, S., Larkin, D.H., Roditty, L., Schoenebeck, G., Tarjan, R.E., Williams, V.V.: Better approximation algorithms for the graph diameter. Proc. SODA 2014, 1041\u20131052 (2014)","journal-title":"Proc. SODA"},{"issue":"1","key":"380_CR17","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 (JACM) 47(1), 132\u2013166 (2000)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"380_CR18","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.2000.1117","volume":"38","author":"E Cohen","year":"2001","unstructured":"Cohen, E., Zwick, U.: All-pairs small-stretch paths. J. Algorithm 38(2), 335\u2013353 (2001)","journal-title":"J. Algorithm"},{"key":"380_CR19","doi-asserted-by":"crossref","unstructured":"Dolev, D., Lenzen, C., Peled, S.: \u201ctri, tri again\u201d: finding triangles and small subgraphs in a distributed setting. In: Proc. DISC, pp. 195\u2013209 (2012)","DOI":"10.1007\/978-3-642-33651-5_14"},{"issue":"5","key":"380_CR20","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"key":"380_CR21","first-page":"367","volume":"2014","author":"A Drucker","year":"2014","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. Proc. PODC 2014, 367\u2013376 (2014)","journal-title":"Proc. PODC"},{"key":"380_CR22","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Distributed exact shortest paths in sublinear time. In: Proc. STOC 2017, pp. 757\u2013770. ACM (2017)","DOI":"10.1145\/3055399.3055452"},{"key":"380_CR23","first-page":"128","volume":"2016","author":"M Elkin","year":"2016","unstructured":"Elkin, M., Neiman, O.: Hopsets with constant hopbound, and applications to approximate shortest paths. Proc. FOCS 2016, 128\u2013137 (2016)","journal-title":"Proc. FOCS"},{"key":"380_CR24","unstructured":"Elkin, M., Neiman, O.: Linear-size hopsets with small hopbound, and distributed routing with low memory (2017). ArXiv:1704.08468 [cs.DS]"},{"key":"380_CR25","unstructured":"Ford Jr., L.R.: Network flow theory. Tech. Rep, Rand Corp Santa Monica, CA (1956)"},{"key":"380_CR26","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1109\/FOCS.2018.00071","volume":"2018","author":"S Forster","year":"2018","unstructured":"Forster, S., Nanongkai, D.: A faster distributed single-source shortest paths algorithm. Proc. FOCS 2018, 686\u2013697 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00071","journal-title":"Proc. FOCS"},{"key":"380_CR27","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1145\/2608628.2608664","volume":"2014","author":"FL Gall","year":"2014","unstructured":"Gall, F.L.: Powers of tensors and fast matrix multiplication. Proc. ISSAC 2014, 296\u2013303 (2014). https:\/\/doi.org\/10.1145\/2608628.2608664","journal-title":"Proc. ISSAC"},{"key":"380_CR28","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1145\/3087801.3087830","volume":"2017","author":"M Ghaffari","year":"2017","unstructured":"Ghaffari, M.: Distributed MIS via all-to-all communication. Proc. PODC 2017, 141\u2013149 (2017). https:\/\/doi.org\/10.1145\/3087801.3087830","journal-title":"Proc. PODC"},{"key":"380_CR29","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1145\/3212734.3212743","volume":"2018","author":"M Ghaffari","year":"2018","unstructured":"Ghaffari, M., Gouleakis, T., Konrad, C., Mitrovic, S., Rubinfeld, R.: Improved massively parallel computation algorithms for MIS, matching, and vertex cover. Proc. PODC 2018, 129\u2013138 (2018). https:\/\/doi.org\/10.1145\/3212734.3212743","journal-title":"Proc. PODC"},{"key":"380_CR30","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/3188745.3188948","volume":"2018","author":"M Ghaffari","year":"2018","unstructured":"Ghaffari, M., Li, J.: Improved distributed algorithms for exact shortest paths. Proc. STOC 2018, 431\u2013444 (2018). https:\/\/doi.org\/10.1145\/3188745.3188948","journal-title":"Proc. STOC"},{"key":"380_CR31","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Nowicki, K.: Congested clique algorithms for the minimum cut problem. In: Proc. PODC 2018, pp. 357\u2013366. ACM (2018)","DOI":"10.1145\/3212734.3212750"},{"key":"380_CR32","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/2933057.2933103","volume":"2016","author":"M Ghaffari","year":"2016","unstructured":"Ghaffari, M., Parter, M.: MST in log-star rounds of congested clique. Proc. PODC 2016, 19\u201328 (2016). https:\/\/doi.org\/10.1145\/2933057.2933103","journal-title":"Proc. PODC"},{"key":"380_CR33","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.tcs.2015.09.029","volume":"608","author":"JW Hegeman","year":"2015","unstructured":"Hegeman, J.W., Pemmaraju, S.V.: Lessons from the congested clique applied to MapReduce. Theoret. Comput. Sci. 608, 268\u2013281 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"380_CR34","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1145\/2897518.2897638","volume":"2016","author":"M Henzinger","year":"2016","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. Proc. STOC 2016, 489\u2013498 (2016). https:\/\/doi.org\/10.1145\/2897518.2897638","journal-title":"Proc. STOC"},{"issue":"6","key":"380_CR35","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/3218657","volume":"65","author":"M Henzinger","year":"2018","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: Decremental single-source shortest paths on undirected graphs in near-linear total update time. J. ACM 65(6), 36 (2018)","journal-title":"J. ACM"},{"key":"380_CR36","doi-asserted-by":"publisher","unstructured":"Holzer, S., Pinsker, N.: Approximation of distances and shortest paths in the broadcast congest clique. In: Proc. OPODIS 2015 (2015). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2015.6","DOI":"10.4230\/LIPIcs.OPODIS.2015.6"},{"key":"380_CR37","first-page":"355","volume":"2012","author":"S Holzer","year":"2012","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. Proc. PODC 2012, 355\u2013364 (2012)","journal-title":"Proc. PODC"},{"key":"380_CR38","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1109\/FOCS.2017.24","volume":"2017","author":"C Huang","year":"2017","unstructured":"Huang, C., Nanongkai, D., Saranurak, T.: Distributed exact weighted all-pairs shortest paths in $$\\tilde{O}(n^{5\/4})$$ rounds. Proc. FOCS 2017, 168\u2013179 (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.24","journal-title":"Proc. FOCS"},{"key":"380_CR39","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.ipl.2018.10.001","volume":"142","author":"SE Huang","year":"2019","unstructured":"Huang, S.E., Pettie, S.: Thorup-zwick emulators are universally optimal hopsets. Inf. Process. Lett. 142, 9\u201313 (2019)","journal-title":"Inf. Process. Lett."},{"key":"380_CR40","first-page":"2620","volume":"2018","author":"T Jurdzi\u0144ski","year":"2018","unstructured":"Jurdzi\u0144ski, T., Nowicki, K.: MST in $${O}(1)$$ rounds of congested clique. Proc. SODA 2018, 2620\u20132632 (2018)","journal-title":"Proc. SODA"},{"key":"380_CR41","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1145\/3210377.3210391","volume":"2018","author":"JH Korhonen","year":"2018","unstructured":"Korhonen, J.H., Suomela, J.: Towards a complexity theory for the congested clique. Proc. SPAA 2018, 163\u2013172 (2018). https:\/\/doi.org\/10.1145\/3210377.3210391","journal-title":"Proc. SPAA"},{"key":"380_CR42","first-page":"57","volume":"2016","author":"F Le Gall","year":"2016","unstructured":"Le Gall, F.: Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. Proc. DISC 2016, 57\u201370 (2016)","journal-title":"Proc. DISC"},{"key":"380_CR43","first-page":"42","volume":"2013","author":"C Lenzen","year":"2013","unstructured":"Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. Proc. PODC 2013, 42\u201350 (2013)","journal-title":"Proc. PODC"},{"key":"380_CR44","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages. In: Proc. STOC 2013, pp. 381\u2013390. ACM (2013)","DOI":"10.1145\/2488608.2488656"},{"key":"380_CR45","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast partial distance estimation and applications. In: Proc. PODC 2015, pp. 153\u2013162. ACM (2015)","DOI":"10.1145\/2767386.2767398"},{"key":"380_CR46","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1145\/2484239.2484262","volume":"2013","author":"C Lenzen","year":"2013","unstructured":"Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. Proc. PODC 2013, 375\u2013382 (2013). https:\/\/doi.org\/10.1145\/2484239.2484262","journal-title":"Proc. PODC"},{"issue":"1","key":"380_CR47","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/S0097539704441848","volume":"35","author":"Z Lotker","year":"2005","unstructured":"Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in $$o(\\log \\log n)$$ communication rounds. SIAM J. Comput. 35(1), 120\u2013131 (2005)","journal-title":"SIAM J. Comput."},{"key":"380_CR48","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proc. STOC 2014, pp. 565\u2013573. ACM (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"380_CR49","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1145\/3210377.3210409","volume":"2018","author":"G Pandurangan","year":"2018","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: On the distributed complexity of large-scale graph computations. Proc. SPAA 2018, 405\u2013414 (2018). https:\/\/doi.org\/10.1145\/3210377.3210409","journal-title":"Proc. SPAA"},{"key":"380_CR50","doi-asserted-by":"publisher","unstructured":"Parter, M.: $${(\\Delta +1)}$$ coloring in the congested clique model. In: Proc. ICALP 2018, pp. 160:1\u2013160:14 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.160","DOI":"10.4230\/LIPIcs.ICALP.2018.160"},{"key":"380_CR51","doi-asserted-by":"publisher","unstructured":"Parter, M., Su, H.: Randomized $$({\\Delta }+1)$$-coloring in $${O}(\\log ^* {\\Delta })$$ congested clique rounds. In: Proc. DISC 2018, pp. 39:1\u201339:18 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.39","DOI":"10.4230\/LIPIcs.DISC.2018.39"},{"key":"380_CR52","doi-asserted-by":"publisher","unstructured":"Parter, M., Yogev, E.: Congested clique algorithms for graph spanners. In: Proc. DISC 2018, pp. 40:1\u201340:18 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.40","DOI":"10.4230\/LIPIcs.DISC.2018.40"},{"key":"380_CR53","first-page":"660","volume":"2012","author":"D Peleg","year":"2012","unstructured":"Peleg, D., Roditty, L., Tal, E.: Distributed algorithms for network diameter and girth. Proc. ICALP 2012, 660\u2013672 (2012)","journal-title":"Proc. ICALP"},{"key":"380_CR54","doi-asserted-by":"crossref","unstructured":"Roditty, L., Vassilevska\u00a0Williams, V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proc. STOC 2013, pp. 515\u2013524. ACM (2013)","DOI":"10.1145\/2488608.2488673"},{"issue":"1","key":"380_CR55","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"},{"key":"380_CR56","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1145\/1109557.1109645","volume":"2006","author":"M Thorup","year":"2006","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. Proc. SODA 2006, 802\u2013809 (2006)","journal-title":"Proc. SODA"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00380-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00380-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00380-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T10:03:01Z","timestamp":1637143381000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00380-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,28]]},"references-count":56,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["380"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00380-5","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,28]]},"assertion":[{"value":"31 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}