{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:54Z","timestamp":1759638294231,"version":"3.37.3"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,7,22]],"date-time":"2017-07-22T00:00:00Z","timestamp":1500681600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1696\/14","1162\/15"],"award-info":[{"award-number":["1696\/14","1162\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s00446-017-0306-2","type":"journal-article","created":{"date-parts":[[2017,7,22]],"date-time":"2017-07-22T10:18:29Z","timestamp":1500718709000},"page":"223-240","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Distributed construction of purely additive spanners"],"prefix":"10.1007","volume":"31","author":[{"given":"Keren","family":"Censor-Hillel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Telikepalli","family":"Kavitha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ami","family":"Paz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Yehudayoff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,22]]},"reference":[{"key":"306_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Bodwin, G.: The 4\/3 additive spanner exponent is tight. In: ACM SIGACT Symposium on Theory of Computing, STOC (2016)","DOI":"10.1145\/2897518.2897555"},{"key":"306_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Bodwin, G.: Error amplification for pairwise spanner lower bounds. In: 27th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA, pp. 841\u2013854 (2016)","DOI":"10.1137\/1.9781611974331.ch60"},{"issue":"4","key":"306_CR3","doi-asserted-by":"crossref","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":"306_CR4","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geometry 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geometry"},{"issue":"3","key":"306_CR5","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.ipl.2007.11.001","volume":"106","author":"S Baswana","year":"2008","unstructured":"Baswana, S.: Streaming algorithm for graph spanners\u2014single pass and constant processing time per edge. Inf. Process. Lett. 106(3), 110\u2013114 (2008)","journal-title":"Inf. Process. Lett."},{"key":"306_CR6","unstructured":"Baswana, S., Sarkar, S.: Fully dynamic algorithm for graph spanners with poly-logarithmic update time. In: 19th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA, pp. 1125\u20131134 (2008)"},{"issue":"4","key":"306_CR7","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S Baswana","year":"2007","unstructured":"Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30(4), 532\u2013563 (2007)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"306_CR8","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/1868237.1868242","volume":"7","author":"S Baswana","year":"2010","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and ( $$\\alpha, \\beta $$ \u03b1 , \u03b2 )-spanners. ACM Trans. Algorithms 7(1), 5 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"306_CR9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/2344422.2344425","volume":"8","author":"S Baswana","year":"2012","unstructured":"Baswana, S., Khurana, S., Sarkar, S.: Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms 8(4), 35 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"306_CR10","doi-asserted-by":"crossref","unstructured":"Bodwin, G., Williams, V.V.: Better distance preservers and additive spanners. In: 27th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA, pp. 855\u2013872 (2016)","DOI":"10.1137\/1.9781611974331.ch61"},{"issue":"4","key":"306_CR11","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1137\/S0895480103431046","volume":"19","author":"B Bollob\u00e1s","year":"2005","unstructured":"Bollob\u00e1s, B., Coppersmith, D., Elkin, M.: Sparse distance preservers and additive spanners. SIAM J. Discrete Math. 19(4), 1029\u20131055 (2005)","journal-title":"SIAM J. Discrete Math."},{"key":"306_CR12","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Ghaffari, M., Kuhn, F.: Distributed connectivity decomposition. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 156\u2013165 (2014)","DOI":"10.1145\/2611462.2611491"},{"key":"306_CR13","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Haeupler, B., Kelner, J.A., Maymounkov, P.: Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In: 44th Symposium on Theory of Computing Conference, STOC, pp. 961\u2013970 (2012)","DOI":"10.1145\/2213977.2214064"},{"key":"306_CR14","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Kavitha, T., Paz, A., Yehudayoff, A.: Distributed construction of purely additive spanners. In: 30th International Symposium on Distributed Computing, DISC, pp. 129\u2013142 (2016)","DOI":"10.1007\/978-3-662-53426-7_10"},{"key":"306_CR15","doi-asserted-by":"crossref","unstructured":"Chechik, S.: Compact routing schemes with improved stretch. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 33\u201341 (2013)","DOI":"10.1145\/2484239.2484268"},{"key":"306_CR16","doi-asserted-by":"crossref","unstructured":"Chechik, S.: New additive spanners. In: 24th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA, pp. 498\u2013512 (2013)","DOI":"10.1137\/1.9781611973105.36"},{"issue":"2","key":"306_CR17","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1137\/050630696","volume":"20","author":"D Coppersmith","year":"2006","unstructured":"Coppersmith, D., Elkin, M.: Sparse sourcewise and pairwise distance preservers. SIAM J. Discrete Math. 20(2), 463\u2013501 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"306_CR18","unstructured":"Cygan, M., Grandoni, F., Kavitha, T.: On pairwise spanners. In: 30th International Symposium on Theoretical Aspects of Computer Science, STACS, pp. 209\u2013220 (2013)"},{"issue":"5","key":"306_CR19","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"A Das Sarma","year":"2012","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"306_CR20","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.tcs.2008.02.019","volume":"399","author":"B Derbel","year":"2008","unstructured":"Derbel, B., Gavoille, C.: Fast deterministic distributed algorithms for sparse spanners. Theor. Comput. Sci. 399(1\u20132), 83\u2013100 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"306_CR21","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg, D.: Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In: 21st International Symposium on Distributed Computing, DISC, pp. 179\u2013192 (2007)","DOI":"10.1007\/978-3-540-75142-7_16"},{"key":"306_CR22","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: On the locality of distributed sparse spanner construction. In: 27th Annual ACM Symposium on Principles of Distributed Computing, PODC, pp. 273\u2013282 (2008)","DOI":"10.1145\/1400751.1400788"},{"key":"306_CR23","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: Local computation of nearly additive spanners. In: 23rd International Symposium on Distributed Computing, DISC, pp. 176\u2013190 (2009)","DOI":"10.1007\/978-3-642-04355-0_20"},{"issue":"5","key":"306_CR24","doi-asserted-by":"crossref","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":"306_CR25","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"issue":"4","key":"306_CR26","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1016\/j.jcss.2005.04.002","volume":"71","author":"DP Dubhashi","year":"2005","unstructured":"Dubhashi, D.P., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J. Comput. Syst. Sci. 71(4), 467\u2013479 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"306_CR27","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Trans. Algorithms 1(2), 283\u2013323 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"306_CR28","doi-asserted-by":"crossref","unstructured":"Elkin, M.: A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In: 26th Annual ACM Symposium on Principles of Distributed Computing, PODC, pp. 185\u2013194 (2007)","DOI":"10.1145\/1281100.1281128"},{"key":"306_CR29","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In: 34th International Colloquium on Automata, Languages and Programming, ICALP, pp. 716\u2013727 (2007)","DOI":"10.1007\/978-3-540-73420-8_62"},{"issue":"3","key":"306_CR30","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: ( $$1+\\epsilon, \\beta $$ 1 + \u03f5 , \u03b2 )-spanner constructions for general graphs. SIAM J. Comput. 33(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"306_CR31","doi-asserted-by":"crossref","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 )$$ ( 1 + \u03f5 , \u03b2 ) -spanners in the distributed and streaming models. Distrib. Comput. 18(5), 375\u2013385 (2006)","journal-title":"Distrib. Comput."},{"key":"306_CR32","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory of Graphs and Its Applications: Proceedings of the Symposium Held in Smolenice in June 1963, pp. 29\u201336. Pub. House of the Czechoslovak Academy of Sciences (1964)","DOI":"10.4064\/cm-13-2-251-254"},{"key":"306_CR33","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: 23rd Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA, pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"key":"306_CR34","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: 27th International Symposium on Distributed Computing, DISC, pp. 1\u201315 (2013)","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"306_CR35","unstructured":"Holzer, S., Pinsker, N.: Approximation of distances and shortest paths in the broadcast congest clique. CoRR, abs\/1412.3445 (2014)"},{"key":"306_CR36","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 355\u2013364 (2012)","DOI":"10.1145\/2332432.2332504"},{"key":"306_CR37","unstructured":"Kavitha, T.: New pairwise spanners. In: 32nd International Symposium on Theoretical Aspects of Computer Science, STACS, pp. 513\u2013526 (2015)"},{"key":"306_CR38","doi-asserted-by":"crossref","unstructured":"Kavitha, T., Varma, N.M.: Small stretch pairwise spanners. In: 40th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 601\u2013612 (2013)","DOI":"10.1007\/978-3-642-39206-1_51"},{"key":"306_CR39","doi-asserted-by":"crossref","unstructured":"Knudsen, M.B.T.: Additive spanners: A simple construction. In: 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT, pp. 277\u2013281 (2014)","DOI":"10.1007\/978-3-319-08404-6_24"},{"key":"306_CR40","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)"},{"key":"306_CR41","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 375\u2013382 (2013)","DOI":"10.1145\/2484239.2484262"},{"key":"306_CR42","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J Matousek","year":"2002","unstructured":"Matousek, J.: Lectures on Discrete Geometry. Springer, New York (2002)"},{"key":"306_CR43","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing-Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing-Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)"},{"key":"306_CR44","doi-asserted-by":"crossref","unstructured":"Parter, M.: Bypassing erd\u0151s\u2019 girth conjecture: Hybrid stretch and sourcewise spanners. In: 41st International Colloquium on Automata, Languages, and Programming, ICALP, pp. 608\u2013619 (2014)","DOI":"10.1007\/978-3-662-43951-7_49"},{"key":"306_CR45","doi-asserted-by":"crossref","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":"306_CR46","doi-asserted-by":"crossref","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed MST construction. In: 40th Annual Symposium on Foundations of Computer Science, FOCS, pp. 253\u2013261 (1999)","DOI":"10.1109\/SFFCS.1999.814597"},{"issue":"1","key":"306_CR47","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"issue":"4","key":"306_CR48","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18(4), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"306_CR49","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"306_CR50","doi-asserted-by":"crossref","unstructured":"Peleg, D., Roditty, L., Tal, E.: Distributed algorithms for network diameter and girth. In: Automata, Languages, and Programming\u201439th International Colloquium, ICALP, pp. 660\u2013672 (2012)","DOI":"10.1007\/978-3-642-31585-5_58"},{"issue":"1","key":"306_CR51","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/1644015.1644022","volume":"6","author":"S Pettie","year":"2009","unstructured":"Pettie, S.: Low distortion spanners. ACM Trans. Algorithms 6(1), 7:1\u20137:22 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"306_CR52","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s00446-009-0091-7","volume":"22","author":"S Pettie","year":"2010","unstructured":"Pettie, S.: Distributed algorithms for ultrasparse spanners and linear size skeletons. Distrib. Comput. 22(3), 147\u2013166 (2010)","journal-title":"Distrib. Comput."},{"issue":"2","key":"306_CR53","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/s00453-010-9401-5","volume":"61","author":"L Roditty","year":"2011","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. Algorithmica 61(2), 389\u2013401 (2011)","journal-title":"Algorithmica"},{"key":"306_CR54","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: 32nd International Colloquium on Automata, Languages and Programming, ICALP, pp. 261\u2013272 (2005)","DOI":"10.1007\/11523468_22"},{"key":"306_CR55","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"306_CR56","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 11\u201324 (2005)","journal-title":"J. ACM"},{"key":"306_CR57","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: 17th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA, pp. 802\u2013809 (2006)","DOI":"10.1145\/1109557.1109645"},{"key":"306_CR58","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: Additive spanners in nearly quadratic time. In: 37th International Colloquium on Automata, Languages and Programming, ICALP, pp. 463\u2013474 (2010)","DOI":"10.1007\/978-3-642-14165-2_40"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0306-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0306-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0306-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,1]],"date-time":"2019-10-01T07:23:08Z","timestamp":1569914588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0306-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,22]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["306"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0306-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,7,22]]}}}