{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T20:55:41Z","timestamp":1725828941571},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_15","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"167-178","source":"Crossref","is-referenced-by-count":10,"title":["Improved Purely Additive Fault-Tolerant Spanners"],"prefix":"10.1007","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luciano","family":"Gual\u00e0","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"issue":"4","key":"15_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":"15_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.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-40450-4_8","volume-title":"Algorithms \u2013 ESA 2013","author":"G. Ausiello","year":"2013","unstructured":"Ausiello, G., Franciosa, P.G., Italiano, G.F., Ribichini, A.: On resilient graph spanners. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 85\u201396. Springer, Heidelberg (2013)"},{"issue":"1","key":"15_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 (alpha, beta)-spanners. ACM Transactions on Algorithms\u00a07(1), 5 (2010)","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"15_CR5","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/s00453-012-9621-y","volume":"66","author":"S. Baswana","year":"2013","unstructured":"Baswana, S., Khanna, N.: Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs. Algorithmica\u00a066(1), 18\u201350 (2013)","journal-title":"Algorithmica"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Karger, D.R.: A nearly optimal oracle for avoiding failed vertices and edges. In: STOC, pp. 101\u2013110 (2009)","DOI":"10.1145\/1536414.1536431"},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/978-3-662-44777-2_12","volume-title":"Algorithms - ESA 2014","author":"D. Bil\u00f2","year":"2014","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Fault-tolerant approximate shortest-path trees. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol.\u00a08737, pp. 137\u2013148. Springer, Heidelberg (2014)"},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-34611-8_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"G. Braunschvig","year":"2012","unstructured":"Braunschvig, G., Chechik, S., Peleg, D.: Fault tolerant additive spanners. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol.\u00a07551, pp. 206\u2013214. Springer, Heidelberg (2012)"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Chechik, S.: New additive spanners. In: SODA, pp. 498\u2013512 (2013)","DOI":"10.1137\/1.9781611973105.36"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: STOC, pp. 435\u2013444 (2009)","DOI":"10.1145\/1536414.1536475"},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-15775-2_8","volume-title":"Algorithms \u2013 ESA 2010","author":"S. Chechik","year":"2010","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: f-sensitivity distance oracles and routing schemes. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 84\u201396. Springer, Heidelberg (2010)"},{"issue":"2","key":"15_CR12","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1137\/050630696","volume":"20","author":"D. Coppersmith","year":"2006","unstructured":"Coppersmith, D., Elkin, M.: Sparse sourcewise and pairwise distance preservers. SIAM J. Discrete Math.\u00a020(2), 463\u2013501 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR13","unstructured":"Cygan, M., Grandoni, F., Kavitha, T.: On pairwise spanners. In: STACS, pp. 209\u2013220 (2013)"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: PODC, pp. 169\u2013178 (2011)","DOI":"10.1145\/1993806.1993830"},{"key":"15_CR15","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications, pp. 29\u201336 (1964)"},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Williams, V.V.: Improved distance sensitivity oracles via fast single-source replacement paths. In: FOCS, pp. 748\u2013757 (2012)","DOI":"10.1109\/FOCS.2012.17"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/978-3-662-45174-8_12","volume-title":"Distributed Computing","author":"M. Parter","year":"2014","unstructured":"Parter, M.: Vertex fault tolerant additive spanners. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol.\u00a08784, pp. 167\u2013181. Springer, Heidelberg (2014)"},{"key":"15_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/978-3-642-40450-4_66","volume-title":"Algorithms \u2013 ESA 2013","author":"M. Parter","year":"2013","unstructured":"Parter, M., Peleg, D.: Sparse fault-tolerant BFS trees. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol.\u00a08125, pp. 779\u2013790. Springer, Heidelberg (2013)"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Parter, M., Peleg, D.: Fault tolerant approximate BFS structures. In: SODA, pp. 1073\u20131092 (2014)","DOI":"10.1137\/1.9781611973402.80"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T19:59:29Z","timestamp":1559246369000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}