{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T01:46:43Z","timestamp":1696643203951},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T00:00:00Z","timestamp":1659571200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T00:00:00Z","timestamp":1659571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2023,9]]},"DOI":"10.1007\/s00446-022-00433-x","type":"journal-article","created":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T09:03:32Z","timestamp":1659603812000},"page":"385-394","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved weighted additive spanners"],"prefix":"10.1007","volume":"36","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Gitlitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,4]]},"reference":[{"key":"433_CR1","doi-asserted-by":"publisher","unstructured":"Ahmed, A.R., Bodwin, G., Sahneh, F.D., Kobourov, S.G., Spence, R.: Weighted additive spanners. In: Adler, I., M\u00fcller, H. (eds.) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers. Lecture Notes in Computer Science, vol. 12301, pp. 401\u2013413 (2020). https:\/\/doi.org\/10.1007\/978-3-030-60440-0_32","DOI":"10.1007\/978-3-030-60440-0_32"},{"issue":"4","key":"433_CR2","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/3088511","volume":"64","author":"A Abboud","year":"2017","unstructured":"Abboud, A., Bodwin, G.: The 4\/3 additive spanner exponent is tight. J. ACM 64(4), 28\u201312820 (2017). https:\/\/doi.org\/10.1145\/3088511","journal-title":"J. ACM"},{"key":"433_CR3","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, 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"key":"433_CR4","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.: Graph spanners. J. Graph Theory 13, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"433_CR5","doi-asserted-by":"publisher","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. Discret. Comput. Geom. 9, 81\u2013100 (1993). https:\/\/doi.org\/10.1007\/BF02189308","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"433_CR6","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). https:\/\/doi.org\/10.1137\/S0097539796303421","journal-title":"SIAM J. Comput."},{"issue":"3","key":"433_CR7","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). https:\/\/doi.org\/10.1137\/S0097539701393384","journal-title":"SIAM J. Comput."},{"key":"433_CR8","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (alpha, beta)-spanners and purely additive spanners. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pp. 672\u2013681 (2005). http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070526"},{"key":"433_CR9","doi-asserted-by":"publisher","unstructured":"Knudsen, M.B.T.: Additive spanners: A simple construction. In: Ravi, R., G\u00f8rtz, I.L. (eds.) Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8503, pp. 277\u2013281 (2014). https:\/\/doi.org\/10.1007\/978-3-319-08404-6_24","DOI":"10.1007\/978-3-319-08404-6_24"},{"key":"433_CR10","doi-asserted-by":"publisher","unstructured":"Chechik, S.: New additive spanners. In: Khanna, S. (ed.) Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pp. 498\u2013512 (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.36","DOI":"10.1137\/1.9781611973105.36"},{"key":"433_CR11","unstructured":"Bodwin, G.: Some general structure for extremal sparsification problems. CoRR arXiv:abs\/2001.07741 (2020)"},{"issue":"1","key":"433_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1644015.1644022","volume":"6","author":"S Pettie","year":"2009","unstructured":"Pettie, S.: Low distortion spanners. ACM Transactions on Algorithms 6(1), 1\u201322 (2009)","journal-title":"ACM Transactions on Algorithms"},{"key":"433_CR13","doi-asserted-by":"publisher","unstructured":"Bodwin, G., Williams, V.V.: Very sparse additive spanners and emulators. In: Roughgarden, T. (ed.) Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pp. 377\u2013382 (2015). https:\/\/doi.org\/10.1145\/2688073.2688103","DOI":"10.1145\/2688073.2688103"},{"key":"433_CR14","doi-asserted-by":"publisher","unstructured":"Bodwin, G., Williams, V.V.: Better distance preservers and additive spanners. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 855\u2013872 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch61","DOI":"10.1137\/1.9781611974331.ch61"},{"key":"433_CR15","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Computing almost shortest paths. In: Proc. 20th ACM Symp. on Principles of Distributed Computing, pp. 53\u201362 (2001)","DOI":"10.1145\/383962.383983"},{"key":"433_CR16","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+\\varepsilon,\\beta )$$-spanners in the distributed and streaming models. Distributed Computing 18, 375\u2013385 (2006)","journal-title":"Distributed Computing"},{"key":"433_CR17","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proc. of Symp. on Discr. Algorithms, pp. 802\u2013809 (2006)","DOI":"10.1145\/1109557.1109645"},{"key":"433_CR18","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 \u201917, pp. 568\u2013576. Society for Industrial and Applied Mathematics, USA (2017)","DOI":"10.1137\/1.9781611974782.36"},{"issue":"4","key":"433_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). https:\/\/doi.org\/10.1137\/18M1166791","journal-title":"SIAM J. Comput."},{"key":"433_CR20","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A tradeoff between size and efficiency for routing tables. J. of the ACM 36, 510\u2013530 (1989)","journal-title":"J. of the ACM"},{"key":"433_CR21","doi-asserted-by":"publisher","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures. SPAA \u201901, pp. 1\u201310. ACM, New York, NY, USA (2001). https:\/\/doi.org\/10.1145\/378580.378581","DOI":"10.1145\/378580.378581"},{"issue":"2","key":"433_CR22","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00446-017-0304-4","volume":"31","author":"M Elkin","year":"2018","unstructured":"Elkin, M., Neiman, O.: On efficient distributed construction of near optimal routing schemes. Distributed Comput. 31(2), 119\u2013137 (2018). https:\/\/doi.org\/10.1007\/s00446-017-0304-4","journal-title":"Distributed Comput."},{"key":"433_CR23","unstructured":"Elkin, M., Gitlitz, Y., Neiman, O.: Almost shortest paths with near-additive error in weighted graphs. CoRR arXiv:abs\/1907.11422 (2019)"},{"key":"433_CR24","doi-asserted-by":"publisher","unstructured":"Ahmed, A.R., Bodwin, G., Hamm, K., Kobourov, S.G., Spence, R.: On additive spanners in weighted graphs with local error. In: Kowalik, L., Pilipczuk, M., Rzazewski, P. (eds.) Graph-Theoretic Concepts in Computer Science - 47th International Workshop, WG 2021, Warsaw, Poland, June 23-25, 2021, Revised Selected Papers. Lecture Notes in Computer Science, vol. 12911, pp. 361\u2013373 (2021). https:\/\/doi.org\/10.1007\/978-3-030-86838-3_28","DOI":"10.1007\/978-3-030-86838-3_28"},{"issue":"4","key":"433_CR25","doi-asserted-by":"publisher","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. Discret. Math. 19(4), 1029\u20131055 (2005). https:\/\/doi.org\/10.1137\/S0895480103431046","journal-title":"SIAM J. Discret. Math."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00433-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-022-00433-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00433-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T18:02:35Z","timestamp":1690826555000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-022-00433-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,4]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["433"],"URL":"https:\/\/doi.org\/10.1007\/s00446-022-00433-x","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,4]]},"assertion":[{"value":"28 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}