{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:10Z","timestamp":1740109270868,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2017,11,15]],"date-time":"2017-11-15T00:00:00Z","timestamp":1510704000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN 2010-2011 ARS Technomedia"],"award-info":[{"award-number":["PRIN 2010-2011 ARS Technomedia"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s00453-017-0396-z","type":"journal-article","created":{"date-parts":[[2017,11,15]],"date-time":"2017-11-15T14:17:16Z","timestamp":1510755436000},"page":"3437-3460","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fault-Tolerant Approximate Shortest-Path Trees"],"prefix":"10.1007","volume":"80","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Luciano","family":"Gual\u00e0","sequence":"additional","affiliation":[]},{"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,15]]},"reference":[{"key":"396_CR1","doi-asserted-by":"crossref","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 Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"396_CR2","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1142\/S1793830910000905","volume":"2","author":"G Ausiello","year":"2010","unstructured":"Ausiello, G., Ribichini, A., Franciosa, P.G., Italiano, G.F.: Computing graph spanners in small memory: fault-tolerance and streaming. Discrete Math. Algorithms Appl. 2(4), 591\u2013606 (2010)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"396_CR3","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Franciosa, P.G., Italiano, G.F., Ribichini, A.: On Resilient Graph Spanners. In: Proceedings of the 21st European Symposium on Algorithms (ESA\u201913). Lecture Notes in Computer Science, vol. 8125, pp. 85\u201396. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_8"},{"key":"396_CR4","doi-asserted-by":"crossref","first-page":"A.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 )$$ ( \u03b1 , \u03b2 ) -spanners. ACM Trans. Algorithms 7, A.5 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"396_CR5","doi-asserted-by":"crossref","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 66(1), 18\u201350 (2013)","journal-title":"Algorithmica"},{"key":"396_CR6","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Karger, D.R.: A nearly optimal oracle for avoiding failed vertices and edges. In: Proceedings of the 41st Symposium on the Theory of Computing (STOC\u201909), pp. 101\u2013110. ACM Press (2009)","DOI":"10.1145\/1536414.1536431"},{"key":"396_CR7","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, D., Grandoni, F., Gual\u00e0, L., Leucci, S., Proietti, G.: Improved purely additive fault-tolerant spanners. In: Proceedings of the 23rd European Symposium on Algorithms (ESA\u201915). Lecture Notes in Computer Science, vol. 9294, pp. 167\u2013178. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_15"},{"key":"396_CR8","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Compact and fast sensitivity oracles for single-source distances. In: Proceedings of the 24th Annual European Symposium on Algorithms (ESA\u201916). Leibniz International Proceedings in Informatics (LIPIcs), vol. 57, pp. 13:1\u201313:14 (2016)"},{"key":"396_CR9","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Multiple-edge-fault-tolerant approximate shortest-path trees. In: Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916). Leibniz International Proceedings in Informatics (LIPIcs), vol. 47, pp. 18:1\u201318:14 (2016)"},{"key":"396_CR10","doi-asserted-by":"crossref","unstructured":"Braunschvig, G., Chechik, S., Peleg, D.: Fault tolerant additive spanners. In: Proceedings of the 38th Workshop on Graph-Theoretic Concepts in Computer Science (WG\u201912). Lecture Notes in Computer Science, vol. 7551, pp. 206\u2013214. Springer (2012)","DOI":"10.1007\/978-3-642-34611-8_22"},{"key":"396_CR11","doi-asserted-by":"crossref","unstructured":"Chechik, S..: New additive spanners. In: Proceedings of the 24th Symposium on Discrete Algorithms (SODA\u201913), pp. 498\u2013512. ACM Press (2013)","DOI":"10.1137\/1.9781611973105.36"},{"key":"396_CR12","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: Proceedings of the 41st Symposium on the Theory of Computing (STOC\u201909), pp. 435\u2013444. ACM press (2009)","DOI":"10.1145\/1536414.1536475"},{"key":"396_CR13","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: $$f$$ f -Sensitivity distance oracles and routing schemes. In: Proceedings of the 18th European Symposium on Algorithms (ESA\u201910). Lecture Notes in Computer Science, vol. 6942, pp. 84\u201396. Springer (2010)","DOI":"10.1007\/978-3-642-15775-2_8"},{"key":"396_CR14","unstructured":"Cygan, M., Grandoni, F., Kavitha, T.: On pairwise spanners. In: Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201913). Leibniz International Proceedings in Informatics (LIPIcs), vol. 20, pp. 209\u2013220 (2013)"},{"key":"396_CR15","doi-asserted-by":"crossref","unstructured":"D\u2019Andrea, A., D\u2019Emidio, M., Frigioni, D., Leucci, S., Proietti, G.: Path-fault-tolerant approximate shortest-path trees. In: Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201915). Lecture Notes in Computer Science, vol. 9439, pp. 224\u2013238. Springer (2015)","DOI":"10.1007\/978-3-319-25258-2_16"},{"issue":"5","key":"396_CR16","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1137\/S0097539705429847","volume":"37","author":"C Demetrescu","year":"2008","unstructured":"Demetrescu, C., Thorup, M., Chowdhury, R.A., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J. Comput. 37(5), 1299\u20131318 (2008)","journal-title":"SIAM J. Comput."},{"key":"396_CR17","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: Proceedings of the 30th Symposium on Principles of Distributed Computing (PODC\u201911), pp. 169\u2013178. ACM Press (2011)","DOI":"10.1145\/1993806.1993830"},{"key":"396_CR18","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Dual-failure distance and connectivity oracles. In: Proceedings of the 20th Symposium on Discrete Algorithms (SODA\u201909), pp. 506\u2013515. ACM Press (2009)","DOI":"10.1137\/1.9781611973068.56"},{"key":"396_CR19","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Proceedings of the Symposium on Theory of Graphs and its Applications, pp. 29\u201336 (1964)"},{"key":"396_CR20","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Williams, V.Vassilevska: Improved distance sensitivity oracles via fast single-source replacement paths. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201912), pp. 748\u2013757 (2012)","DOI":"10.1109\/FOCS.2012.17"},{"issue":"4","key":"396_CR21","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/s00453-003-1024-7","volume":"36","author":"E Nardelli","year":"2003","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica 36(4), 361\u2013374 (2003)","journal-title":"Algorithmica"},{"issue":"1","key":"396_CR22","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0304-3975(02)00438-3","volume":"296","author":"E Nardelli","year":"2003","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Finding the most vital node of a shortest path. Theor. Comput. Sci. 296(1), 167\u2013177 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"396_CR23","doi-asserted-by":"crossref","unstructured":"Parter, M.: Vertex fault tolerant additive spanners. In: Proceedings of the 28th International Symposium on Distributed Computing (DISC\u201914). Lecture Notes in Computer Science, vol. 8784, pp. 167\u2013181. Springer (2014)","DOI":"10.1007\/978-3-662-45174-8_12"},{"key":"396_CR24","doi-asserted-by":"crossref","unstructured":"Parter, M.: Dual failure resilient BFS structure. In: Proceedings of the 34th Symposium on Principles of Distributed Computing (PODC\u201915), pp. 481\u2013490. ACM Press (2015)","DOI":"10.1145\/2767386.2767408"},{"key":"396_CR25","unstructured":"Parter, M.: Fault-tolerant logical network structures. Bull. EATCS. 118, 75\u2013100 (2016)"},{"key":"396_CR26","doi-asserted-by":"crossref","unstructured":"Parter, M., Peleg, D.: Sparse fault-tolerant BFS trees. In: Proceedings of the 21st European Symposium on Algorithms (ESA\u201913). Lecture Notes in Computer Science, vol. 8125 , pp. 779\u2013790. Springer (2013)","DOI":"10.1007\/978-3-642-40450-4_66"},{"key":"396_CR27","doi-asserted-by":"crossref","unstructured":"Parter, M., Peleg, D.: Fault tolerant approximate BFS structures. In: Proceedings of the 25th Symposium on Discrete Algorithms (SODA\u201914), pp. 1073\u20131092. ACM Press (2014)","DOI":"10.1137\/1.9781611973402.80"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0396-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0396-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0396-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,6]],"date-time":"2019-10-06T01:49:57Z","timestamp":1570326597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0396-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,15]]},"references-count":27,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["396"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0396-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,11,15]]}}}