{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:53:35Z","timestamp":1725490415712},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_9","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T14:58:43Z","timestamp":1188053923000},"page":"78-89","source":"Crossref","is-referenced-by-count":16,"title":["Low Distortion Spanners"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"9_CR1","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. SIAM J.\u00a0Comput\u00a028(4), 1167\u20131181 (1999)","journal-title":"SIAM J.\u00a0Comput"},{"key":"9_CR2","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., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete and Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete and Computational Geometry"},{"key":"9_CR3","first-page":"804","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J.\u00a0ACM\u00a032, 804\u2013823 (1985)","journal-title":"J.\u00a0ACM"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: FOCS 2006, (2006)","DOI":"10.1109\/FOCS.2006.29"},{"key":"9_CR5","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (\u03b1,\u03b2)-spanners and purely additive spanners. In: SODA 2005, (2005)"},{"issue":"4","key":"9_CR6","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1137\/S0895480103431046","volume":"9","author":"B. Bollob\u00e1s","year":"2006","unstructured":"Bollob\u00e1s, B., Coppersmith, D., Elkin, M.: Sparse subgraphs that preserve long distances and additive spanners. SIAM J. Discr. Math.\u00a09(4), 1029\u20131055 (2006)","journal-title":"SIAM J. Discr. Math."},{"key":"9_CR7","unstructured":"Coppersmith, D., Elkin, M.: Sparse source-wise and pair-wise distance preservers. In: SODA 2005 (2005)"},{"key":"9_CR8","unstructured":"Coppersmith, D., Elkin, M.: Sparse source-wise and pair-wise preservers. SIAM J. Discrete Math (to appear)"},{"issue":"1","key":"9_CR9","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. J.\u00a0Algor.\u00a050(1), 79\u201395 (2004)","journal-title":"J.\u00a0Algor."},{"issue":"5","key":"9_CR10","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.\u00a0Comput.\u00a029(5), 1740\u20131759 (2000)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"3","key":"9_CR11","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 constructions for general graphs. SIAM J.\u00a0Comput.\u00a033(3), 608\u2013631 (2004)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Elkin, M., Zhang, J.: Efficient algorithms for constructing (1\u2009+\u2009\u03b5,\u03b2)-spanners in the distributed and streaming models. In: PODC 2004 (2004)","DOI":"10.1145\/1011767.1011791"},{"issue":"3","key":"9_CR13","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J. Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a069(3), 485\u2013497 (2004)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"key":"9_CR14","unstructured":"Halperin, S., Zwick, U.: Unpublished result (1996)"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Narasimhan, G., Smid, M.: Geometric Spanner Networks (2007)","DOI":"10.1017\/CBO9780511546884"},{"key":"9_CR16","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. J. Graph Theory \u00a013, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"9_CR17","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.\u00a0Comput.\u00a018, 740\u2013747 (1989)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9_CR18","unstructured":"Pettie, S.: Low distortion spanners. See, http:\/\/www.eecs.umich.edu\/~pettie"},{"key":"9_CR19","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. In: SODA 2002 (2002)"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: STOC 2004 (2004)","DOI":"10.1145\/1007352.1007372"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA 2001 (2001)","DOI":"10.1145\/378580.378581"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: SODA 2006 (2006)","DOI":"10.1145\/1109557.1109645"},{"key":"9_CR23","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\u201324 (2005)","journal-title":"J.ACM"},{"issue":"1","key":"9_CR24","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0095-8956(91)90097-4","volume":"52","author":"R. Wenger","year":"1991","unstructured":"Wenger, R.: Extremal graphs with no C 4\u2019s, C 6\u2019s, or C 10\u2019s. J. Combin. Theory Ser. B\u00a052(1), 113\u2013116 (1991)","journal-title":"J. Combin. Theory Ser. B"},{"key":"9_CR25","doi-asserted-by":"crossref","unstructured":"Woodruff, D.: Lower bounds for additive spanners, emulators, and more. In: FOCS 2006 (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-540-73420-8_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:11:31Z","timestamp":1619518291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}