{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T09:21:59Z","timestamp":1778664119097,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,12,15]],"date-time":"2016-12-15T00:00:00Z","timestamp":1481760000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00224-016-9736-7","type":"journal-article","created":{"date-parts":[[2016,12,15]],"date-time":"2016-12-15T06:06:28Z","timestamp":1481781988000},"page":"1011-1036","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["New Pairwise Spanners"],"prefix":"10.1007","volume":"61","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,15]]},"reference":[{"key":"9736_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Bodwin, G.: Lower bound amplification theorems for graph spanners. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 841\u2013856 (2016)","DOI":"10.1137\/1.9781611974331.ch60"},{"key":"9736_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Bodwin, G.: The 4\/3 additive spanner exponent is tight. To appear in the Proceedings of the 48th Annual Symposium on the Theory of Computing (STOC), 351\u2013361 (2016)","DOI":"10.1145\/2897518.2897555"},{"issue":"4","key":"9736_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":"9736_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., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discret. Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Discret. Comput. Geom."},{"issue":"1","key":"9736_CR5","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1137\/S0097539794271898","volume":"28","author":"B Awerbuch","year":"1998","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear time construction of sparse neighborhood covers. SIAM J. Comput. 28(1), 263\u2013277 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9736_CR6","first-page":"151","volume":"5","author":"B Awerbuch","year":"1992","unstructured":"Awerbuch, B., Peleg, D.: Routing with polynomial communication-space trade-off. SIAM J. Comput. 5(2), 151\u2013162 (1992)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"9736_CR7","doi-asserted-by":"crossref","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":"9736_CR8","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and (\u03b1,\u03b2)-spanners. ACM Transactions on Algorithms, 7(1) (2010)","DOI":"10.1145\/1868237.1868242"},{"issue":"4","key":"9736_CR9","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S Baswana","year":"2006","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in o(n 2 n) time. ACM Trans. Algorithms 2(4), 557\u2013577 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"9736_CR10","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 linear time algorithm for computing a (2k\u22121)-spanner of o(n 1+1\/k ) size in weighted graphs. Random Struct. Algoritm. 30(4), 532\u2013563 (2007)","journal-title":"Random Struct. Algoritm."},{"key":"9736_CR11","doi-asserted-by":"crossref","unstructured":"Bodwin, G., Vassilevska Williams, V.: Better distance preservers and additive spanners. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 855\u2013872 (2016)","DOI":"10.1137\/1.9781611974331.ch61"},{"issue":"4","key":"9736_CR12","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. Discret. Math. 19(4), 1029\u20131055 (2005)","journal-title":"SIAM J. Discret. Math."},{"key":"9736_CR13","doi-asserted-by":"crossref","unstructured":"Chechik, S.: New additive spanners. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 498\u2013512 (2013)","DOI":"10.1137\/1.9781611973105.36"},{"issue":"3","key":"9736_CR14","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"9736_CR15","doi-asserted-by":"crossref","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths of stretch t. In: Proceedings of the 34th IEEE Symp. on Foundations of Computer Science (FOCS), pp 648\u2013658 (1993)","DOI":"10.1109\/SFCS.1993.366822"},{"key":"9736_CR16","unstructured":"Coppersmith, D., Elkin, M.: Sparse source-wise and pair-wise distance preservers. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 660\u2013669 (2005)"},{"key":"9736_CR17","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"28","author":"LJ Cowen","year":"2001","unstructured":"Cowen, L.J.: Compact routing with minimum stretch. J. Algorithms 28, 170\u2013183 (2001)","journal-title":"J. Algorithms"},{"issue":"1","key":"9736_CR18","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jalgor.2003.08.001","volume":"50","author":"LJ Cowen","year":"2004","unstructured":"Cowen, L.J., Wagner, C.G.: Compact roundtrip routing in directed networks. J. Algorithms 50(1), 79\u201395 (2004)","journal-title":"J. Algorithms"},{"key":"9736_CR19","unstructured":"Cygan, M., Grandoni, F., Kavitha, T.: On pairwise spanners. In: Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), pp 209\u2013220 (2013)"},{"issue":"5","key":"9736_CR20","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D Dor","year":"2004","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29(5), 1740\u20131759 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9736_CR21","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"},{"issue":"3","key":"9736_CR22","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: (1 + \ud835\udf16,\u03b2)-spanner construction for general graphs. SIAM J. Comput. 33(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput."},{"key":"9736_CR23","unstructured":"Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 210\u2013219 (2001)"},{"key":"9736_CR24","unstructured":"Halperin, S., Zwick, U.: Unpublished result (1996)"},{"key":"9736_CR25","unstructured":"Kavitha, T.: New pairwise spanners. In: Proceedings of the 32th International Symposium on Theoretical Aspects of Computer Science (STACS), pp 513\u2013526 (2015)"},{"issue":"4","key":"9736_CR26","doi-asserted-by":"crossref","first-page":"2239","DOI":"10.1137\/140953927","volume":"29","author":"T Kavitha","year":"2015","unstructured":"Kavitha, T., Varma, N.M.: Small stretch pairwise spanners. SIAM J. Discret. Math. 29(4), 2239\u20132254 (2015)","journal-title":"SIAM J. Discret. Math."},{"key":"9736_CR27","doi-asserted-by":"crossref","unstructured":"Knudsen, M.B.T.: Additive spanners: a simple construction. In: Proc. 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp 277\u2013281 (2014)","DOI":"10.1007\/978-3-319-08404-6_24"},{"key":"9736_CR28","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discret. Math. 13, 383\u2013390 (1975)","journal-title":"Discret. Math."},{"key":"9736_CR29","doi-asserted-by":"crossref","unstructured":"Parter, M.: Bypassing Erdo\u0307s\u2019 girth conjecture: Hybrid spanners and sourcewise spanners. In: Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), pp 608\u2013619 (2014)","DOI":"10.1007\/978-3-662-43951-7_49"},{"issue":"3","key":"9736_CR30","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-preserving labeling schemes. J. Graph Theory 33(3), 167\u2013176 (2000)","journal-title":"J. Graph Theory"},{"key":"9736_CR31","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Schaffer, A.A.: Graph spanners. J. Graph Theory 13, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"9736_CR32","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, 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"key":"9736_CR33","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Low distortion spanners. ACM Transactions on Algorithms, 6(1) (2009)","DOI":"10.1145\/1644015.1644022"},{"key":"9736_CR34","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Proceedings of the 32nd Int. Colloq. on Automata, Languages, and Programming (ICALP), pp 261\u2013272 (2005)","DOI":"10.1007\/11523468_22"},{"key":"9736_CR35","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA), pp 580\u2013591 (2004)","DOI":"10.1007\/978-3-540-30140-0_52"},{"issue":"1","key":"9736_CR36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"9736_CR37","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 802\u2013809 (2006)","DOI":"10.1145\/1109557.1109645"},{"key":"9736_CR38","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: Additive spanners in nearly quadratic time. In: Proceedings of the 37th Int. Colloq. on Automata, Languages, and Programming (ICALP), pp 463\u2013474 (2010)","DOI":"10.1007\/978-3-642-14165-2_40"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9736-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9736-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9736-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:58:49Z","timestamp":1749833929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9736-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,15]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["9736"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9736-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,15]]}}}