{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:30:15Z","timestamp":1725456615934},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642346101"},{"type":"electronic","value":"9783642346118"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34611-8_22","type":"book-chapter","created":{"date-parts":[[2012,10,22]],"date-time":"2012-10-22T08:42:25Z","timestamp":1350895345000},"page":"206-214","source":"Crossref","is-referenced-by-count":9,"title":["Fault Tolerant Additive Spanners"],"prefix":"10.1007","author":[{"given":"Gilad","family":"Braunschvig","sequence":"first","affiliation":[]},{"given":"Shiri","family":"Chechik","sequence":"additional","affiliation":[]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"22_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 (without matrix multiplication). SIAM J. Comput.\u00a028(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"22_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 & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proc. IEEE Symp. on Foundations of Computer Science (FOCS), pp. 591\u2013602 (2006)","DOI":"10.1109\/FOCS.2006.29"},{"key":"22_CR4","first-page":"5","volume":"7","author":"S. Baswana","year":"2010","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and (\u03b1, \u03b2)-spanners. ACM Trans. on Algo.\u00a07, A.5 (2010)","journal-title":"ACM Trans. on Algo."},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: Proc. 41st ACM Symp. on Theory of Computing (STOC), pp. 435\u2013444 (2009)","DOI":"10.1145\/1536414.1536475"},{"key":"22_CR6","first-page":"2004","volume":"32","author":"A. Czumaj","year":"2003","unstructured":"Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discrete & Computational Geometry\u00a032, 2004 (2003)","journal-title":"Discrete & Computational Geometry"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-Tolerant Spanners: Better and Simpler. In: 30th ACM Symp. on Principles of Distributed Computing (PODC), pp. 169\u2013178 (2011)","DOI":"10.1145\/1993806.1993830"},{"issue":"5","key":"22_CR8","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. Computing\u00a029(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Computing"},{"issue":"3","key":"22_CR9","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. Computing\u00a033(3), 608\u2013631 (2004)","journal-title":"SIAM J. Computing"},{"issue":"2","key":"22_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0166-218X(03)00259-2","volume":"137","author":"A.M. Farley","year":"2004","unstructured":"Farley, A.M., Proskurowski, A., Zappala, D., Windisch, K.: Spanners and message distribution in networks. Discrete Applied Mathematics\u00a0137(2), 159\u2013171 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.: Efficient algorithms for constructing fault-tolerant geometric spanners. In: Proc. 30th ACM Symp. on Theory of Computing (STOC), pp. 186\u2013195 (1998)","DOI":"10.1145\/276698.276734"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-48447-7_20","volume-title":"Algorithms and Data Structures","author":"T. Lukovszki","year":"1999","unstructured":"Lukovszki, T.: New Results on Fault Tolerant Geometric Spanners. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 193\u2013204. Springer, Heidelberg (1999)"},{"issue":"2","key":"22_CR13","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. Computing\u00a018(2), 740\u2013747 (1989)","journal-title":"SIAM J. Computing"},{"issue":"3","key":"22_CR14","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":"22_CR15","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Low distortion spanners. ACM Transactions on Algorithms\u00a06(1) (2009)","DOI":"10.1145\/1644015.1644022"},{"key":"22_CR16","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)"},{"key":"22_CR17","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proc. 13th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"22_CR18","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":"22_CR19","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: 17th Symp. on Discrete Algorithms (SODA), pp. 802\u2013809. ACM-SIAM (2006)","DOI":"10.1145\/1109557.1109645"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34611-8_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:00:44Z","timestamp":1620133244000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34611-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642346101","9783642346118"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34611-8_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}