{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T10:37:26Z","timestamp":1773830246656,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":53,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662534250","type":"print"},{"value":"9783662534267","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53426-7_10","type":"book-chapter","created":{"date-parts":[[2016,9,3]],"date-time":"2016-09-03T08:49:15Z","timestamp":1472892555000},"page":"129-142","source":"Crossref","is-referenced-by-count":8,"title":["Distributed Construction of Purely Additive Spanners"],"prefix":"10.1007","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":[[2016,9,4]]},"reference":[{"key":"10_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":"10_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Bodwin, G.: Error amplification for pairwise spanner lower bounds. In: Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2016)","DOI":"10.1137\/1.9781611974331.ch60"},{"issue":"4","key":"10_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":"10_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. Geom. 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"10_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 - single pass and constant processing time per edge. Inf. Process. Lett. 106(3), 110\u2013114 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"10_CR6","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)-spanners. ACM Trans. Algorithms 7(1), 5 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"10_CR7","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":"10_CR8","unstructured":"Baswana, S., Sarkar, S.: Fully dynamic algorithm for graph spanners with poly-logarithmic update time. In: ACM-SIAM Symposium on Discrete Algorithms, SODA (2008)"},{"issue":"4","key":"10_CR9","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. Algorithm 30(4), 532\u2013563 (2007)","journal-title":"Random Struct. Algorithm"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Bodwin, G., Williams, V.V.: Better distance preservers and additive spanners. In: ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 855\u2013872 (2016)","DOI":"10.1137\/1.9781611974331.ch61"},{"issue":"4","key":"10_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":"10_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 (2014)","DOI":"10.1145\/2611462.2611491"},{"key":"10_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: Symposium on Theory of Computing Conference, STOC, 2012","DOI":"10.1145\/2213977.2214064"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Chechik, S.: Compact routing schemes with improved stretch. In: ACM Symposium on Principles of Distributed Computing, PODC (2013)","DOI":"10.1145\/2484239.2484268"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Chechik, S.: New additive spanners. In: ACM-SIAM Symposium on Discrete Algorithms, SODA (2013)","DOI":"10.1137\/1.9781611973105.36"},{"issue":"2","key":"10_CR16","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":"10_CR17","unstructured":"Cygan, M., Grandoni, F., Kavitha, T.: On pairwise spanners. In: Symposium on Theoretical Aspects of Computer Science, STACS (2013)"},{"issue":"5","key":"10_CR18","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":"10_CR19","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":"10_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-3-540-75142-7_16","volume-title":"Distributed Computing","author":"B Derbel","year":"2007","unstructured":"Derbel, B., Gavoille, C., Peleg, D.: Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In: Pelc, A. (ed.) DISC 2007. LNCS, vol. 4731, pp. 179\u2013192. Springer, Heidelberg (2007)"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: On the locality of distributed sparse spanner construction. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 273\u2013282 (2008)","DOI":"10.1145\/1400751.1400788"},{"key":"10_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1007\/978-3-642-04355-0_20","volume-title":"Distributed Computing","author":"B Derbel","year":"2009","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: Local computation of nearly additive spanners. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 176\u2013190. Springer, Heidelberg (2009)"},{"issue":"5","key":"10_CR23","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":"10_CR24","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 (2014)","DOI":"10.1145\/2611462.2611493"},{"issue":"4","key":"10_CR25","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":"10_CR26","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. Algorithm 1(2), 283\u2013323 (2005)","journal-title":"ACM Trans. Algorithm"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Elkin, M.: A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 185\u2013194 (2007)","DOI":"10.1145\/1281100.1281128"},{"key":"10_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1007\/978-3-540-73420-8_62","volume-title":"Automata, Languages and Programming","author":"M Elkin","year":"2007","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 716\u2013727. Springer, Heidelberg (2007)"},{"issue":"3","key":"10_CR29","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)-spanner constructions for general graphs. SIAM J. Comput. 33(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10_CR30","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)-spanners in the distributed and streaming models. Distrib. Comput. 18(5), 375\u2013385 (2006)","journal-title":"Distrib. Comput."},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"key":"10_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-642-41527-2_1","volume-title":"Distributed Computing","author":"M Ghaffari","year":"2013","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Afek, Y. (ed.) DISC 2013. LNCS, vol. 8205, pp. 1\u201315. Springer, Heidelberg (2013)"},{"key":"10_CR33","unstructured":"Holzer, S., Pinsker, N.: Approximation of distances and shortest paths in the broadcast congest clique. CoRR, abs\/1412.3445 (2014)"},{"key":"10_CR34","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 (2012)","DOI":"10.1145\/2332432.2332504"},{"key":"10_CR35","unstructured":"Kavitha, T.: New pairwise spanners. In: Symposium on Theoretical Aspects of Computer Science, STACS, pp. 513\u2013526 (2015)"},{"key":"10_CR36","doi-asserted-by":"crossref","unstructured":"Kavitha, T., Varma, N.M.: Small stretch pairwise spanners. In: International Colloquium on Automata, Languages, and Programming, ICALP (2013)","DOI":"10.1007\/978-3-642-39206-1_51"},{"key":"10_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/978-3-319-08404-6_24","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"MBT Knudsen","year":"2014","unstructured":"Knudsen, M.B.T.: Additive spanners: a simple construction. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 277\u2013281. Springer, Heidelberg (2014)"},{"key":"10_CR38","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 (2013)","DOI":"10.1145\/2484239.2484262"},{"key":"10_CR39","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":"10_CR40","doi-asserted-by":"crossref","unstructured":"Parter, M.: Bypassing Erd\u0151s\u2019 girth conjecture: hybrid stretch and sourcewise spanners. In: International Colloquium on Automata, Languages and Programming, ICALP (2014)","DOI":"10.1007\/978-3-662-43951-7_49"},{"key":"10_CR41","series-title":"SIAM Monographs on Discrete Mathematics and Applications","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. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"10_CR42","doi-asserted-by":"crossref","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed MST construction. In: Symposium on Foundations of Computer Science, FOCS, pp. 253\u2013261 (1999)","DOI":"10.1109\/SFFCS.1999.814597"},{"issue":"1","key":"10_CR43","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":"10_CR44","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":"10_CR45","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":"10_CR46","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Low distortion spanners. ACM Trans. Algorithms 6(1) (2009)","DOI":"10.1145\/1644015.1644022"},{"issue":"3","key":"10_CR47","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."},{"key":"10_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/11523468_22","volume-title":"Automata, Languages and Programming","author":"L Roditty","year":"2005","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"issue":"2","key":"10_CR49","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":"10_CR50","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: ACM Symposium on Parallel Algorithms and Architectures, SPAA, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"10_CR51","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 113\u2013116 (2005)","journal-title":"J. ACM"},{"key":"10_CR52","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 802\u2013809 (2006)","DOI":"10.1145\/1109557.1109645"},{"key":"10_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/978-3-642-14165-2_40","volume-title":"Automata, Languages and Programming","author":"DP Woodruff","year":"2010","unstructured":"Woodruff, D.P.: Additive spanners in nearly quadratic time. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 463\u2013474. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53426-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T05:47:36Z","timestamp":1568353656000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53426-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662534250","9783662534267"],"references-count":53,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53426-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}