{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:44Z","timestamp":1740109304971,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T00:00:00Z","timestamp":1635552000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T00:00:00Z","timestamp":1635552000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/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 \u201cARS TechnoMedia\u201d"],"award-info":[{"award-number":["PRIN 2010 \u201cARS TechnoMedia\u201d"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014810","name":"Fondazione di Sardegna","doi-asserted-by":"crossref","award":["Algorithms for (fault-tolerant) pairwise spanners and distance oracles"],"award-info":[{"award-number":["Algorithms for (fault-tolerant) pairwise spanners and distance oracles"]}],"id":[{"id":"10.13039\/100014810","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,1]]},"DOI":"10.1007\/s00453-021-00879-8","type":"journal-article","created":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T07:02:54Z","timestamp":1635577374000},"page":"37-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees"],"prefix":"10.1007","volume":"84","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Luciano","family":"Gual\u00e0","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8848-7006","authenticated-orcid":false,"given":"Stefano","family":"Leucci","sequence":"additional","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,30]]},"reference":[{"key":"879_CR1","doi-asserted-by":"crossref","unstructured":"Ahmed, A.R., Bodwin, G., Sahneh, F.D., Hamm, K., Jebelli, M.J.L., Kobourov, S.G., Spence, R.: Graph spanners: a tutorial review. arXiv:1909.03152 (2019)","DOI":"10.1016\/j.cosrev.2020.100253"},{"issue":"2","key":"879_CR2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1145\/1103963.1103966","volume":"1","author":"S Alstrup","year":"2005","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1(2), 243\u2013264 (2005). https:\/\/doi.org\/10.1145\/1103963.1103966","journal-title":"ACM Trans. Algorithms"},{"key":"879_CR3","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 Comput. Geom. 9, 81\u2013100 (1993). https:\/\/doi.org\/10.1007\/BF02189308","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"879_CR4","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1007\/s00453-015-0006-x","volume":"74","author":"G Ausiello","year":"2016","unstructured":"Ausiello, G., Franciosa, P.G., Italiano, G.F., Ribichini, A.: On resilient graph spanners. Algorithmica 74(4), 1363\u20131385 (2016). https:\/\/doi.org\/10.1007\/s00453-015-0006-x","journal-title":"Algorithmica"},{"issue":"1","key":"879_CR5","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1137\/16M1087643","volume":"47","author":"S Baswana","year":"2018","unstructured":"Baswana, S., Choudhary, K., Roditty, L.: Fault-tolerant subgraph for single-source reachability: general and optimal. SIAM J. Comput. 47(1), 80\u201395 (2018). https:\/\/doi.org\/10.1137\/16M1087643","journal-title":"SIAM J. Comput."},{"issue":"1","key":"879_CR6","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 66(1), 18\u201350 (2013). https:\/\/doi.org\/10.1007\/s00453-012-9621-y","journal-title":"Algorithmica"},{"issue":"1","key":"879_CR7","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1868237.1868242","volume":"7","author":"S Baswana","year":"2010","unstructured":"Baswana, S., Telikepalli, K., Mehlhorn, K., Pettie, S.: Additive spanners and (alpha, beta)-spanners. ACM Trans. Algorithms 7(1), 5 (2010). https:\/\/doi.org\/10.1145\/1868237.1868242","journal-title":"ACM Trans. Algorithms"},{"key":"879_CR8","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":"879_CR9","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, D., Choudhary, K., Gual\u00e0, L., Leucci, S., Parter, M., Proietti, G.: Efficient oracles and routing schemes for replacement paths. In: 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, pp. 13:1\u201313:15 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.13","DOI":"10.4230\/LIPIcs.STACS.2018.13"},{"key":"879_CR10","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, D., Grandoni, F., Gual\u00e0, L., Leucci, S., Proietti, G.: Improved purely additive fault-tolerant spanners. In: ESA, pp. 167\u2013178 (2015)","DOI":"10.1007\/978-3-662-48350-3_15"},{"key":"879_CR11","doi-asserted-by":"publisher","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Compact and Fast Sensitivity Oracles for Single-Source Distances. In: 24th Annual European Symposium on Algorithms (ESA 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a057, pp. 13:1\u201313:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.13. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/6364","DOI":"10.4230\/LIPIcs.ESA.2016.13"},{"issue":"12","key":"879_CR12","doi-asserted-by":"publisher","first-page":"3437","DOI":"10.1007\/s00453-017-0396-z","volume":"80","author":"D Bil\u00f2","year":"2018","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Leucci, S., Proietti, G.: Fault-tolerant approximate shortest-path trees. Algorithmica 80(12), 3437\u20133460 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0396-z","journal-title":"Algorithmica"},{"key":"879_CR13","unstructured":"Bodwin, G., Grandoni, F., Parter, M., Williams, V.V.: Preserving distances in very faulty graphs. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, pp. 73:1\u201373:14 (2017). 10.4230\/LIPIcs.ICALP.2017.73"},{"key":"879_CR14","doi-asserted-by":"crossref","unstructured":"Bodwin, G., Patel, S.: A trivial yet optimal solution to vertex fault tolerant spanners. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019., pp. 541\u2013543 (2019). 10.1145\/3293611.3331588","DOI":"10.1145\/3293611.3331588"},{"key":"879_CR15","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2015.02.036","volume":"580","author":"G Braunschvig","year":"2015","unstructured":"Braunschvig, G., Chechik, S., Peleg, D., Sealfon, A.: Fault tolerant additive and ($$\\mu $$, $$\\alpha $$)-spanners. Theor. Comput. Sci. 580, 94\u2013100 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.02.036","journal-title":"Theor. Comput. Sci."},{"key":"879_CR16","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Mozes, S., Tebeka, B.: Exact distance oracles for planar graphs with failing vertices. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pp. 2110\u20132123 (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.127","DOI":"10.1137\/1.9781611975482.127"},{"issue":"6","key":"879_CR17","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B Chazelle","year":"2000","unstructured":"Chazelle, B.: A minimum spanning tree algorithm with inverse-ackermann type complexity. J. ACM 47(6), 1028\u20131047 (2000). https:\/\/doi.org\/10.1145\/355541.355562","journal-title":"J. ACM"},{"key":"879_CR18","doi-asserted-by":"publisher","unstructured":"Chechik, S.: New additive spanners. In: SODA, pp. 498\u2013512 (2013). https:\/\/doi.org\/10.1137\/1.9781611973105.36","DOI":"10.1137\/1.9781611973105.36"},{"key":"879_CR19","doi-asserted-by":"publisher","unstructured":"Chechik, S.: Approximate distance oracles with constant query time. In: STOC, pp. 654\u2013663 (2014). https:\/\/doi.org\/10.1145\/2591796.2591801","DOI":"10.1145\/2591796.2591801"},{"issue":"4","key":"879_CR20","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1007\/s00453-011-9543-0","volume":"63","author":"S Chechik","year":"2012","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: f-sensitivity distance oracles and routing schemes. Algorithmica 63(4), 861\u2013882 (2012). https:\/\/doi.org\/10.1007\/s00453-011-9543-0","journal-title":"Algorithmica"},{"key":"879_CR21","doi-asserted-by":"publisher","unstructured":"D\u2019Andrea, A., D\u2019Emidio, M., Frigioni, D., Leucci, S., Proietti, G.: Path-fault-tolerant approximate shortest-path trees. In: SIROCCO, pp. 224\u2013238 (2015). https:\/\/doi.org\/10.1007\/978-3-319-25258-2_16","DOI":"10.1007\/978-3-319-25258-2_16"},{"key":"879_CR22","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Dual-failure distance and connectivity oracles. In: SODA, pp. 506\u2013515 (2009). http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496826","DOI":"10.1137\/1.9781611973068.56"},{"key":"879_CR23","doi-asserted-by":"publisher","unstructured":"Elkin, M., Pettie, S.: A linear-size logarithmic stretch path-reporting distance oracle for general graphs. ACM Trans. Algorithms 12(4), 50:1-50:31 (2016). https:\/\/doi.org\/10.1145\/2888397","DOI":"10.1145\/2888397"},{"issue":"2","key":"879_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jagm.1994.1033","volume":"17","author":"D Eppstein","year":"1994","unstructured":"Eppstein, D.: Offline algorithms for dynamic minimum spanning tree problems. J. Algorithms 17(2), 237\u2013250 (1994). https:\/\/doi.org\/10.1006\/jagm.1994.1033","journal-title":"J. Algorithms"},{"issue":"5","key":"879_CR25","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification: a technique for speeding up dynamic graph algorithms. J. ACM 44(5), 669\u2013696 (1997). https:\/\/doi.org\/10.1145\/265910.265914","journal-title":"J. ACM"},{"key":"879_CR26","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications, pp. 29\u201336 (1964)"},{"issue":"4","key":"879_CR27","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"GN Frederickson","year":"1985","unstructured":"Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781\u2013798 (1985). https:\/\/doi.org\/10.1137\/0214055","journal-title":"SIAM J. Comput."},{"key":"879_CR28","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":"879_CR29","doi-asserted-by":"publisher","unstructured":"Gupta, M., Khan, S.: Multiple source dual fault tolerant BFS trees. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pp. 127:1\u2013127:15 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.127","DOI":"10.4230\/LIPIcs.ICALP.2017.127"},{"key":"879_CR30","doi-asserted-by":"publisher","unstructured":"Gupta, M., Singh, A.: Generic single edge fault tolerant exact distance oracle. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pp. 72:1\u201372:15 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.72","DOI":"10.4230\/LIPIcs.ICALP.2018.72"},{"issue":"1","key":"879_CR31","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms 41(1), 69\u201385 (2001). https:\/\/doi.org\/10.1006\/jagm.2001.1171","journal-title":"J. Algorithms"},{"issue":"2","key":"879_CR32","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984). https:\/\/doi.org\/10.1137\/0213024","journal-title":"SIAM J. Comput."},{"issue":"2","key":"879_CR33","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S0097539797327209","volume":"31","author":"MR Henzinger","year":"2001","unstructured":"Henzinger, M.R., King, V.: Maintaining minimum spanning forests in dynamic graphs. SIAM J. Comput. 31(2), 364\u2013374 (2001). https:\/\/doi.org\/10.1137\/S0097539797327209","journal-title":"SIAM J. Comput."},{"issue":"4","key":"879_CR34","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001). https:\/\/doi.org\/10.1145\/502090.502095","journal-title":"J. ACM"},{"key":"879_CR35","doi-asserted-by":"crossref","unstructured":"Jordan, C.: Sur les assemblages de lignes. (1869)","DOI":"10.1515\/crll.1869.70.185"},{"key":"879_CR36","unstructured":"Knuth, D.E.: The art of computer programming, Volume I: Fundamental Algorithms, 3rd Edition. Addison-Wesley (1997). https:\/\/www.worldcat.org\/oclc\/312910844"},{"issue":"1","key":"879_CR37","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/s00453-002-0988-z","volume":"35","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 35(1), 56\u201374 (2003)","journal-title":"Algorithmica"},{"key":"879_CR38","doi-asserted-by":"crossref","unstructured":"Parter, M.: Dual failure resilient BFS structure. In: PODC, pp. 481\u2013490 (2015)","DOI":"10.1145\/2767386.2767408"},{"key":"879_CR39","unstructured":"Parter, M.: Fault-tolerant logical network structures. Bulletin of the EATCS 118 (2016). http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/403"},{"issue":"5","key":"879_CR40","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s00446-015-0252-9","volume":"30","author":"M Parter","year":"2017","unstructured":"Parter, M.: Vertex fault tolerant additive spanners. Distrib. Comput. 30(5), 357\u2013372 (2017). https:\/\/doi.org\/10.1007\/s00446-015-0252-9","journal-title":"Distrib. Comput."},{"key":"879_CR41","doi-asserted-by":"publisher","unstructured":"Parter, M., Peleg, D.: Sparse fault-tolerant BFS structures. ACM Trans. Algorithms 13(1), 11:1-11:24 (2016). https:\/\/doi.org\/10.1145\/2976741","DOI":"10.1145\/2976741"},{"key":"879_CR42","doi-asserted-by":"publisher","unstructured":"Parter, M., Peleg, D.: Fault-tolerant approximate BFS structures. ACM Trans. Algorithms 14(1), 10:1-10:15 (2018). https:\/\/doi.org\/10.1145\/3022730","DOI":"10.1145\/3022730"},{"key":"879_CR43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25209-0","author":"P Sanders","year":"2019","unstructured":"Sanders, P., Mehlhorn, K., Dietzfelbinger, M., Dementiev, R.: Sequential and parallel algorithms and data structures: the basic toolbox. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-25209-0","journal-title":"Springer"},{"issue":"1","key":"879_CR44","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 52(1), 1\u201324 (2005). https:\/\/doi.org\/10.1145\/1044731.1044732","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00879-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00879-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00879-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T14:05:58Z","timestamp":1643033158000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00879-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,30]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["879"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00879-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,10,30]]},"assertion":[{"value":"31 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}