{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:34Z","timestamp":1763468134430},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_51","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"601-612","source":"Crossref","is-referenced-by-count":10,"title":["Small Stretch Pairwise Spanners"],"prefix":"10.1007","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nithin M.","family":"Varma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"51_CR1","doi-asserted-by":"publisher","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 Journal on Computing\u00a028(1), 263\u2013277 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"51_CR2","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0405013","volume":"5","author":"B. Awerbuch","year":"1992","unstructured":"Awerbuch, B., Peleg, D.: Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Math\u00a05(2), 151\u2013162 (1992)","journal-title":"SIAM Journal on Discrete Math"},{"issue":"7","key":"51_CR3","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 Journal on Computing\u00a039(7), 2865\u20132896 (2010)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"51_CR4","doi-asserted-by":"publisher","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 (\u03b1,\u03b2)-Spanners. ACM Transactions on Algorithms\u00a07(1), 5 (2010)","journal-title":"ACM Transactions on Algorithms"},{"key":"51_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-45061-0_32","volume-title":"Automata, Languages and Programming","author":"S. Baswana","year":"2003","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k\u2009\u2212\u20091)-spanner of O(n\n                  1\u2009+\u20091\/k\n                  ) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 384\u2013396. Springer, Heidelberg (2003)"},{"key":"51_CR6","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in O(n\n                  2logn) time. In: Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 271\u2013280 (2004)"},{"key":"51_CR7","unstructured":"Bollob\u00e1s, B., Coppersmith, D., Elkin, M.: Sparse Distance Preservers and Additive Spanners. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 414\u2013423 (2003)"},{"key":"51_CR8","doi-asserted-by":"crossref","unstructured":"Chechik, S.: New Additive Spanners. In: Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 498\u2013512 (2013)","DOI":"10.1137\/1.9781611973105.36"},{"key":"51_CR9","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths of stretch t. In: Proc. 34th IEEE Symp. on Foundations of Computer Science (FOCS), pp. 648\u2013658 (1993)"},{"key":"51_CR10","unstructured":"Coppersmith, D., Elkin, M.: Sparse source-wise and pair-wise distance preservers. In: Proc. 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 660\u2013669 (2005)"},{"key":"51_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"28","author":"L.J. Cowen","year":"2001","unstructured":"Cowen, L.J.: Compact routing with minimum stretch. Journal of Algorithms\u00a028, 170\u2013183 (2001)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"51_CR12","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jalgor.2003.08.001","volume":"50","author":"L.J. Cowen","year":"2004","unstructured":"Cowen, L.J., Wagner, C.G.: Compact roundtrip routing in directed networks. Journal of Algorithms\u00a050(1), 79\u201395 (2004)","journal-title":"Journal of Algorithms"},{"key":"51_CR13","unstructured":"Cygan, M., Grandoni, F., Kavitha, T.: On Pairwise Spanners. In: Proc. 30th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 209\u2013220 (2013)"},{"issue":"5","key":"51_CR14","doi-asserted-by":"publisher","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 Journal on Computing\u00a029(5), 1740\u20131759 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"51_CR15","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Transactions on Algorithms\u00a01(2), 283\u2013323 (2005)","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"51_CR16","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M. Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: (1\u2009+\u2009\u03b5, \u03b2)-spanner construction for general graphs. SIAM Journal on Computing\u00a033(3), 608\u2013631 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"51_CR17","unstructured":"Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. In: Proc. 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 210\u2013219 (2001)"},{"key":"51_CR18","unstructured":"Halperin, S., Zwick, U.: Unpublished result (1996)"},{"issue":"3","key":"51_CR19","doi-asserted-by":"publisher","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. Journal of Graph Theory\u00a033(3), 167\u2013176 (2000)","journal-title":"Journal of Graph Theory"},{"key":"51_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Schaffer, A.A.: Graph Spanners. Journal of Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"key":"51_CR21","doi-asserted-by":"publisher","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 Journal on Computing\u00a018, 740\u2013747 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"51_CR22","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Low Distortion Spanners. ACM Transactions on Algorithms\u00a06(1) (2009)","DOI":"10.1145\/1644015.1644022"},{"key":"51_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/978-3-540-30140-0_52","volume-title":"Algorithms \u2013 ESA 2004","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 580\u2013591. Springer, Heidelberg (2004)"},{"key":"51_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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.\u00a03580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"issue":"1","key":"51_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate Distance Oracles. Journal of the ACM\u00a052(1), 1\u201324 (2005)","journal-title":"Journal of the ACM"},{"key":"51_CR26","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":"51_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/978-3-642-14165-2_40","volume-title":"Automata, Languages and Programming","author":"D.P. 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.\u00a06198, pp. 463\u2013474. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T09:28:22Z","timestamp":1557912502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}