{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:56:25Z","timestamp":1758272185844},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_20","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"196-207","source":"Crossref","is-referenced-by-count":19,"title":["Spanners with Slack"],"prefix":"10.1007","author":[{"given":"T. -H. Hubert","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Dinitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (2006)","DOI":"10.1145\/1132516.1132557"},{"key":"20_CR2","first-page":"83","volume-title":"FOCS 2005: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science","author":"I. Abraham","year":"2005","unstructured":"Abraham, I., Bartal, Y., Chan, H.T.-H., Dhamdhere, K., Gupta, A., Kleinberg, J.M., Neiman, O., Slivkins, A.: Metric embeddings with relaxed guarantees. In: FOCS 2005: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 83\u2013100. IEEE Computer Society, Washington (2005)"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete Comput. Geom.\u00a09(1) (1993)","DOI":"10.1007\/BF02189308"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.H.M.: Euclidean spanners: short, thin, and lanky. In: STOC (1995)","DOI":"10.1145\/225058.225191"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"20_CR6","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (\u03b1, \u03b2)-spanners and purely additive spanners. In: SODA, pp. 672\u2013681 (2005)"},{"key":"20_CR7","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in \u00f5(n2) time. In: Proceedings of the\u00a015th\u00a0Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 271\u2013280 (2004)"},{"key":"20_CR8","first-page":"414","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"B. Bollob\u00e1s","year":"2003","unstructured":"Bollob\u00e1s, B., Coppersmith, D., Elkin, M.: Sparse distance preservers and additive spanners (extended abstract). In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 2003, pp. 414\u2013423. ACM, New York (2003)"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Bourgain, J.: On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel Journal of Mathematics\u00a052(1-2) (1985)","DOI":"10.1007\/BF02776078"},{"key":"20_CR10","unstructured":"Chan, H.T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in DOubling metrics. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (2005)"},{"key":"#cr-split#-20_CR11.1","doi-asserted-by":"crossref","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. Internat. J. Comput. Geom. Appl.??5(1-2) (1995);","DOI":"10.1142\/S0218195995000088"},{"key":"#cr-split#-20_CR11.2","unstructured":"In: Eighth Annual ACM Symposium on Computational Geometry, Berlin (1992)"},{"issue":"3-4","key":"20_CR12","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/s004530010016","volume":"27","author":"S. Chaudhuri","year":"2000","unstructured":"Chaudhuri, S., Zaroliagis, C.D.: Shortest paths in digraphs of small treewidth. I. Sequential algorithms. Algorithmica\u00a027(3-4), 212\u2013226 (2000) (Treewidth)","journal-title":"Algorithmica"},{"key":"20_CR13","unstructured":"Coppersmith, D., Elkin, M.: Sparse source-wise and pair-wise distance preservers. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (2005)"},{"issue":"3","key":"20_CR14","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. Comput (electronic)\u00a033(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput. (electronic)"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the Annual ACM Symposium on Theory of Computing (2003)","DOI":"10.1145\/780542.780608"},{"key":"20_CR16","unstructured":"Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (2001)"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.H.M.: Approximate distance oracles for geometric graphs. In: SODA, pp. 828\u2013837 (2002)","DOI":"10.1007\/3-540-36136-7_32"},{"issue":"2","key":"20_CR18","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1137\/S0097539702409927","volume":"34","author":"A. Gupta","year":"2004","unstructured":"Gupta, A., Kumar, A., Rastogi, R.: Traveling with a Pez dispenser (or, routing issues in MPLS). SIAM J. Comput (electronic)\u00a034(2), 453\u2013474 (2004\/2005)","journal-title":"SIAM J. Comput. (electronic)"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. In: Symposium on Computational Geometry, pp. 150\u2013158 (2005)","DOI":"10.1145\/1064092.1064117"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithmic aspects of geometric embeddings. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (2001)","DOI":"10.1109\/SFCS.2001.959878"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M., Slivkins, A., Wexler, T.: Triangulation and embedding using small sets of beacons. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (2004)","DOI":"10.1109\/FOCS.2004.70"},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46784-X_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Peleg","year":"1999","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665. Springer, Heidelberg (1999)"},{"key":"20_CR23","unstructured":"Peleg, D.: Distributed computing. Society for Industrial and Applied Mathematics (SIAM), A locality-sensitive approach (2000)"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory\u00a013(1) (1989)","DOI":"10.1002\/jgt.3190130114"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: Algorithms for low-dimensional metrics. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (2004)","DOI":"10.1145\/1007352.1007399"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (2001)","DOI":"10.1109\/SFCS.2001.959898"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (2001)","DOI":"10.1145\/380752.380798"},{"key":"20_CR28","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"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:40:26Z","timestamp":1605642026000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11841036_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}