{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T03:05:46Z","timestamp":1725937546845},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319720494"},{"type":"electronic","value":"9783319720500"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-72050-0_18","type":"book-chapter","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T11:57:13Z","timestamp":1514548633000},"page":"303-317","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Effective Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges"],"prefix":"10.1007","author":[{"given":"Davide","family":"Bil\u00f2","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feliciano","family":"Colella","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":[[2017,12,30]]},"reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-319-25258-2_17","volume-title":"Structural Information and Communication Complexity","author":"D Bil\u00f2","year":"2015","unstructured":"Bil\u00f2, D., Colella, F., Gual\u00e0, L., Leucci, S., Proietti, G.: A faster computation of all the best swap edges of a tree spanner. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 239\u2013253. Springer, Cham (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-319-25258-2_17"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-662-48350-3_15","volume-title":"Algorithms \u2013 ESA 2015","author":"D Bil\u00f2","year":"2015","unstructured":"Bil\u00f2, D., Grandoni, F., Gual\u00e0, L., Leucci, S., Proietti, G.: Improved purely additive fault-tolerant spanners. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 167\u2013178. Springer, Heidelberg (2015). \nhttps:\/\/doi.org\/10.1007\/978-3-662-48350-3_15"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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. 8737, pp. 137\u2013148. Springer, Heidelberg (2014). \nhttps:\/\/doi.org\/10.1007\/978-3-662-44777-2_12"},{"issue":"2","key":"18_CR4","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s00453-012-9674-y","volume":"68","author":"D Bil\u00f2","year":"2014","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Proietti, G.: Finding best swap edges minimizing the routing cost of a spanning tree. Algorithmica 68(2), 337\u2013357 (2014)","journal-title":"Algorithmica"},{"issue":"3","key":"18_CR5","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1007\/s00453-014-9912-6","volume":"73","author":"D Bil\u00f2","year":"2015","unstructured":"Bil\u00f2, D., Gual\u00e0, L., Proietti, G.: A faster computation of all the best swap edges of a shortest paths tree. Algorithmica 73(3), 547\u2013570 (2015)","journal-title":"Algorithmica"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, 31 May\u20132 June 2009, pp. 435\u2013444 (2009)","DOI":"10.1145\/1536414.1536475"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-642-38233-8_11","volume-title":"Algorithms and Complexity","author":"AK Datta","year":"2013","unstructured":"Datta, A.K., Larmore, L.L., Pagli, L., Prencipe, G.: Linear time distributed swap edge algorithms. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 122\u2013133. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-38233-8_11"},{"issue":"1","key":"18_CR8","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2007.03.046","volume":"383","author":"A Salvo Di","year":"2007","unstructured":"Di Salvo, A., Proietti, G.: Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor. Theor. Comput. Sci. 383(1), 23\u201333 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"18_CR9","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 2011, San Jose, CA, USA, 6\u20138 June 2011, pp. 169\u2013178 (2011)","DOI":"10.1145\/1993806.1993830"},{"key":"18_CR10","series-title":"IFIP International Federation for Information Processing","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/1-4020-8141-3_14","volume-title":"Exploring New Frontiers of Theoretical Informatics","author":"P Flocchini","year":"2004","unstructured":"Flocchini, P., Enriques, A.M., Pagli, L., Prencipe, G., Santoro, N.: Efficient protocols for computing the optimal swap edges of a shortest path tree. In: Levy, J.-J., Mayr, E.W., Mitchell, J.C. (eds.) TCS 2004. IIFIP, vol. 155, pp. 153\u2013166. Springer, Boston, MA (2004). \nhttps:\/\/doi.org\/10.1007\/1-4020-8141-3_14"},{"issue":"2","key":"18_CR11","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1093\/ietisy\/e89-d.2.700","volume":"89\u2013D","author":"P Flocchini","year":"2006","unstructured":"Flocchini, P., Enriques, A.M., Pagli, L., Prencipe, G., Santoro, N.: Point-of-failure shortest-path rerouting: computing the optimal swap edges distributively. IEICE Trans. 89\u2013D(2), 700\u2013708 (2006)","journal-title":"IEICE Trans."},{"issue":"7","key":"18_CR12","doi-asserted-by":"crossref","first-page":"976","DOI":"10.1016\/j.jpdc.2008.03.002","volume":"68","author":"P Flocchini","year":"2008","unstructured":"Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Widmayer, P.: Computing all the best swap edges distributively. J. Parallel Distrib. Comput. 68(7), 976\u2013983 (2008)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"3","key":"18_CR13","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s00453-007-9016-7","volume":"49","author":"L Gual\u00e0","year":"2007","unstructured":"Gual\u00e0, L., Proietti, G.: Exact and approximate truthful mechanisms for the shortest paths tree problem. Algorithmica 49(3), 171\u2013191 (2007)","journal-title":"Algorithmica"},{"issue":"3","key":"18_CR14","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/PL00009225","volume":"22","author":"GF Italiano","year":"1998","unstructured":"Italiano, G.F., Ramaswami, R.: Maintaining spanning trees of small diameter. Algorithmica 22(3), 275\u2013304 (1998)","journal-title":"Algorithmica"},{"issue":"3","key":"18_CR15","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.tcs.2004.06.033","volume":"333","author":"H Ito","year":"2005","unstructured":"Ito, H., Iwama, K., Okabe, Y., Yoshihiro, T.: Single backup table schemes for shortest-path routing. Theor. Comput. Sci. 333(3), 347\u2013353 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"185","key":"18_CR16","first-page":"81","volume":"70","author":"C Jordan","year":"1869","unstructured":"Jordan, C.: Sur les assemblages de lignes. J. Reine Angew. Math 70(185), 81 (1869)","journal-title":"J. Reine Angew. Math"},{"issue":"2","key":"18_CR17","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0020-0190(00)00175-7","volume":"79","author":"E Nardelli","year":"2001","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: A faster computation of the most vital edge of a shortest path. Inf. Process. Lett. 79(2), 81\u201385 (2001)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"18_CR18","doi-asserted-by":"crossref","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":"18_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1007\/11602613_96","volume-title":"Algorithms and Computation","author":"S Pettie","year":"2005","unstructured":"Pettie, S.: Sensitivity analysis of minimum spanning trees in sub-inverse-ackermann time. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 964\u2013973. Springer, Heidelberg (2005). \nhttps:\/\/doi.org\/10.1007\/11602613_96"},{"issue":"1","key":"18_CR20","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"RE Tarjan","year":"1982","unstructured":"Tarjan, R.E.: Sensitivity analysis of minimum spanning trees and shortest path trees. Inf. Process. Lett. 14(1), 30\u201333 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"18_CR21","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s00453-007-9080-z","volume":"50","author":"BY Wu","year":"2008","unstructured":"Wu, B.Y., Hsiao, C.Y., Chao, K.M.: The swap edges of a multiple-sources routing tree. Algorithmica 50(3), 299\u2013311 (2008)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-72050-0_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T12:02:54Z","timestamp":1514548974000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-72050-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319720494","9783319720500"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-72050-0_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}