{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,4]],"date-time":"2026-01-04T02:45:10Z","timestamp":1767494710242},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_40","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T09:26:02Z","timestamp":1278321962000},"page":"463-474","source":"Crossref","is-referenced-by-count":13,"title":["Additive Spanners in Nearly Quadratic Time"],"prefix":"10.1007","author":[{"given":"David P.","family":"Woodruff","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D.: On space-stretch trade-offs: upper bounds. In: SPAA, pp. 217\u2013224 (2006)","DOI":"10.1145\/1148109.1148144"},{"issue":"4","key":"40_CR2","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.\u00a028(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and (\u03b1, \u03b2)-spanners. ACM Transactions on Algorithms (2009)","DOI":"10.1145\/1868237.1868242"},{"key":"40_CR4","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: FOCS, pp. 591\u2013602 (2006)","DOI":"10.1109\/FOCS.2006.29"},{"key":"40_CR5","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (alpha, beta)-spanners and purely additive spanners. In: SODA, pp. 672\u2013681 (2005)"},{"key":"40_CR6","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in \u00f5(n\n                    \n                      \n                    \n                    $^{\\mbox{2}}$\n                  ) time. In: SODA, pp. 271\u2013280 (2004)"},{"issue":"1","key":"40_CR7","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch. SIAM J. Comput.\u00a028(1), 210\u2013236 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"40_CR8","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1145\/331605.331610","volume":"47","author":"E. Cohen","year":"2000","unstructured":"Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM\u00a047(1), 132\u2013166 (2000)","journal-title":"J. ACM"},{"key":"40_CR9","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press & McGraw-Hill Book Company (2001)"},{"issue":"1","key":"40_CR10","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L. Cowen","year":"2001","unstructured":"Cowen, L.: Compact routing with minimum stretch. J. Algorithms\u00a038(1), 170\u2013183 (2001)","journal-title":"J. Algorithms"},{"issue":"1","key":"40_CR11","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jalgor.2003.08.001","volume":"50","author":"L. Cowen","year":"2004","unstructured":"Cowen, L., Wagner, C.G.: Compact roundtrip routing in directed networks. J. Algorithms\u00a050(1), 79\u201395 (2004)","journal-title":"J. Algorithms"},{"issue":"5","key":"40_CR12","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.\u00a029(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"key":"40_CR13","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Personal communication (2009)","DOI":"10.12968\/sece.2009.1.1424"},{"issue":"2","key":"40_CR14","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":"40_CR15","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.\u00a033(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"40_CR16","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 J. Comput.\u00a018(4), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"40_CR17","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 trade-off between space and efficiency for routing tables. J. ACM\u00a036(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"40_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-73420-8_9","volume-title":"Automata, Languages and Programming","author":"S. Pettie","year":"2007","unstructured":"Pettie, S.: Low distortion spanners. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 78\u201389. Springer, Heidelberg (2007)"},{"key":"40_CR19","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.\u00a03580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"40_CR21","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. J. ACM\u00a052(1), 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"40_CR22","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: SODA, pp. 802\u2013809 (2006)","DOI":"10.1145\/1109557.1109645"},{"key":"40_CR23","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: Lower bounds for additive spanners, emulators, and more. In: FOCS, pp. 389\u2013398 (2006)","DOI":"10.1109\/FOCS.2006.45"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T15:40:32Z","timestamp":1558280432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}