{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T01:11:51Z","timestamp":1767834711388,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,5,2]],"date-time":"2015-05-02T00:00:00Z","timestamp":1430524800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Italian Ministry of Education, University, and Research (MIUR) under national research project \u201cAMANDA \u2013 Algorithmics for MAssive and Networked DAta\u201d"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00453-015-0006-x","type":"journal-article","created":{"date-parts":[[2015,5,1]],"date-time":"2015-05-01T13:25:35Z","timestamp":1430486735000},"page":"1363-1385","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On Resilient Graph Spanners"],"prefix":"10.1007","volume":"74","author":[{"given":"Giorgio","family":"Ausiello","sequence":"first","affiliation":[]},{"given":"Paolo G.","family":"Franciosa","sequence":"additional","affiliation":[]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Ribichini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,5,2]]},"reference":[{"issue":"4","key":"6_CR1","doi-asserted-by":"crossref","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. 28(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"6_CR2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I Althofer","year":"1993","unstructured":"Althofer, 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":"2","key":"6_CR3","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1007\/s00453-008-9216-9","volume":"55","author":"G Ausiello","year":"2009","unstructured":"Ausiello, G., Demetrescu, C., Franciosa, P.G., Italiano, G.F., Ribichini, A.: Graph spanners in the streaming model: an experimental study. Algorithmica 55(2), 346\u2013374 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"6_CR4","doi-asserted-by":"crossref","first-page":"365","DOI":"10.7155\/jgaa.00133","volume":"10","author":"G Ausiello","year":"2006","unstructured":"Ausiello, G., Franciosa, P.G., Italiano, G.F.: Small stretch spanners on dynamic graphs. J. Graph Algorithms Appl. 10(2), 365\u2013385 (2006)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"6_CR5","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1142\/S1793830910000905","volume":"2","author":"G Ausiello","year":"2010","unstructured":"Ausiello, G., Franciosa, P.G., Italiano, G.F., Ribichini, A.: Computing graph spanner in small memory: fault-tolerance and streaming. Discrete Math. Algorithms Appl. 2(4), 591\u2013605 (2010)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Baswana, S.: Dynamic algorithms for graph spanners. In: Proceedings of 13th Annual European Symposium on Algorithms (ESA\u201906), pp. 76\u201387 (2006)","DOI":"10.1007\/11841036_10"},{"issue":"1","key":"6_CR7","doi-asserted-by":"crossref","first-page":"5:1","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 Trans. Algorithms 7(1), 5:1\u20135:26 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"6_CR8","doi-asserted-by":"crossref","first-page":"35:1","DOI":"10.1145\/2344422.2344425","volume":"8","author":"S Baswana","year":"2012","unstructured":"Baswana, S., Khurana, S., Sarkar, S.: Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms 8(4), 35:1\u201335:51 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"6_CR9","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"JA Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. J. Comb. Theory Ser. B 16(2), 97\u2013105 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Braunschvig, G., Chechik, S., Peleg, D.: Fault tolerant additive spanners. In: Graph-Theoretic Concepts in Computer Science\u201438th International Workshop, (WG\u201912), volume 7551 of LNCS, pp 206\u2013214. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-34611-8_22"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Chechik, S.: New additive spanners. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913), pp. 498\u2013512 (2013)","DOI":"10.1137\/1.9781611973105.36"},{"issue":"7","key":"6_CR12","doi-asserted-by":"crossref","first-page":"3403","DOI":"10.1137\/090758039","volume":"39","author":"S Chechik","year":"2010","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault tolerant spanners for general graphs. SIAM J. Comput. 39(7), 3403\u20133423 (2010)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"6_CR13","doi-asserted-by":"crossref","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. 20(2), 463\u2013501 (2006)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"6_CR14","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":"6_CR15","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC\u201911), pp. 169\u2013178 (2011)","DOI":"10.1145\/1993806.1993830"},{"issue":"5","key":"6_CR16","doi-asserted-by":"crossref","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. Comput. 29(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"6_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1921659.1921666","volume":"7","author":"M Elkin","year":"2011","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms 7(2), 1\u201317 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"6_CR18","unstructured":"Halperin, S., Zwick, U.: Linear time deterministic algorithm for computing spanners for unweighted graphs (1996) (unpublished manuscript)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Jacob, R., Kosch\u00fctzki, D., Lehmann, K.A., Peeters, L., Tenfelde-Podehl, D.: Algorithms for centrality indices. In: Brandes, U., Erlebach, T. (eds.) Network Analysis, volume 3418 of LNCS, pp. 62\u201382. Springer, Berlin (2005)","DOI":"10.1007\/978-3-540-31955-9_4"},{"issue":"1","key":"6_CR20","doi-asserted-by":"crossref","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"T K\u0151v\u00e1ri","year":"1954","unstructured":"K\u0151v\u00e1ri, T., S\u00f3s, V.T., Tur\u00e1n, P.: On a problem of K. Zarankiewicz. Colloq. Math. 3(1), 50\u201357 (1954)","journal-title":"Colloq. Math."},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Kosch\u00fctzki, D., Lehmann, K.A., Peeters, L., Richter, S., Tenfelde-Podehl, D., Zlotowski, O.: Centrality indices. In: Brandes, U., Erlebach, T. (eds.) Network Analysis, volume 3418 of LNCS, pp. 16\u201361. Springer, Berlin (2005)","DOI":"10.1007\/978-3-540-31955-9_3"},{"key":"6_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J Matou\u0161ek","year":"2002","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer, Berlin (2002)"},{"issue":"1\u20132","key":"6_CR23","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1006\/game.1999.0790","volume":"35","author":"N Nisan","year":"2001","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35(1\u20132), 166\u2013196 (2001)","journal-title":"Games Econ. Behav."},{"key":"6_CR24","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sh\u00e4ffer, A.: Graph spanners. J. Graph Theory 13, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP\u201905), volume 3580 of LNCS, pp. 261\u2013272. Springer, Berlin (2005)","DOI":"10.1007\/11523468_22"},{"key":"6_CR26","first-page":"301","volume":"2","author":"K Zarankiewicz","year":"1951","unstructured":"Zarankiewicz, K.: Problem p 101. Colloq. Math. 2, 301 (1951)","journal-title":"Colloq. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0006-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0006-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0006-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,24]],"date-time":"2019-08-24T11:46:32Z","timestamp":1566647192000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0006-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,2]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["6"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0006-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,2]]}}}