{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:34:49Z","timestamp":1725744889439},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_8","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"85-96","source":"Crossref","is-referenced-by-count":1,"title":["On Resilient Graph Spanners"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Ausiello","sequence":"first","affiliation":[]},{"given":"Paolo Giulio","family":"Franciosa","sequence":"additional","affiliation":[]},{"given":"Giuseppe Francesco","family":"Italiano","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Ribichini","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"8_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":"8_CR2","doi-asserted-by":"publisher","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 & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"8_CR3","doi-asserted-by":"publisher","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\u00a055(2), 346\u2013374 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"8_CR4","doi-asserted-by":"publisher","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. Journal of Graph Algorithms and Applications\u00a010(2), 365\u2013385 (2006)","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"4","key":"8_CR5","doi-asserted-by":"publisher","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 Mathematics, Algorithms and Applications\u00a02(4), 591\u2013605 (2010)","journal-title":"Discrete Mathematics, Algorithms and Applications"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/11841036_10","volume-title":"Algorithms \u2013 ESA 2006","author":"S. Baswana","year":"2006","unstructured":"Baswana, S.: Dynamic algorithms for graph spanners. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 76\u201387. Springer, Heidelberg (2006)"},{"key":"8_CR7","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (\u03b1, \u03b2)-spanners and purely additive spanners. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 672\u2013681 (2005)"},{"issue":"4","key":"8_CR8","doi-asserted-by":"crossref","first-page":"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\u00a08(4), 35:1\u201335:51 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"8_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0095-8956(74)90052-5","volume":"16","author":"J.A. Bondy","year":"1974","unstructured":"Bondy, J.A., Simonovits, M.: Cycles of even length in graphs. Journal of Combinatorial Theory, Series B\u00a016(2), 97\u2013105 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"8_CR10","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":"8_CR11","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: Proc. of 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp. 435\u2013444 (2009)","DOI":"10.1145\/1536414.1536475"},{"issue":"2","key":"8_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."},{"issue":"5","key":"8_CR13","doi-asserted-by":"publisher","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.\u00a037(5), 1299\u20131318 (2008)","journal-title":"SIAM J. Comput."},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: Proc. of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC 2011), pp. 169\u2013178 (2011)","DOI":"10.1145\/1993806.1993830"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1007\/978-3-540-73420-8_62","volume-title":"Automata, Languages and Programming","author":"M. Elkin","year":"2007","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 716\u2013727. Springer, Heidelberg (2007)"},{"issue":"3","key":"8_CR16","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M. Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: (1+epsilon, beta)-spanner constructions for general graphs. SIAM J. Comput.\u00a033(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput."},{"key":"8_CR17","unstructured":"Halperin, S., Zwick, U.: Linear time deterministic algorithm for computing spanners for unweighted graphs. Unpublished manuscript (1996)"},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/978-3-540-31955-9_4","volume-title":"Network Analysis","author":"R. Jacob","year":"2005","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. LNCS, vol.\u00a03418, pp. 62\u201382. Springer, Heidelberg (2005)"},{"issue":"1","key":"8_CR19","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. Colloquium Mathematicae\u00a03(1), 50\u201357 (1954)","journal-title":"Colloquium Mathematicae"},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-31955-9_3","volume-title":"Network Analysis","author":"D. Kosch\u00fctzki","year":"2005","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. LNCS, vol.\u00a03418, pp. 16\u201361. Springer, Heidelberg (2005)"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Springer (2002)","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"8_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-73420-8_9","volume-title":"Automata, Languages and Programming","author":"S. Pettie","year":"2007","unstructured":"Pettie, S.: Low distortion spanners. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 78\u201389. Springer, Heidelberg (2007)"},{"key":"8_CR23","first-page":"301","volume":"2","author":"K. Zarankiewicz","year":"1951","unstructured":"Zarankiewicz, K.: Problem p 101. Colloquium Mathematicae\u00a02, 301 (1951)","journal-title":"Colloquium Mathematicae"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T12:44:42Z","timestamp":1558010682000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}