{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T22:34:27Z","timestamp":1725834867841},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319252575"},{"type":"electronic","value":"9783319252582"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-25258-2_16","type":"book-chapter","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T03:10:18Z","timestamp":1445224218000},"page":"224-238","source":"Crossref","is-referenced-by-count":1,"title":["Path-Fault-Tolerant Approximate Shortest-Path Trees"],"prefix":"10.1007","author":[{"given":"Annalisa","family":"D\u2019Andrea","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mattia","family":"D\u2019Emidio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniele","family":"Frigioni","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":[[2015,11,20]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"R. Albert","year":"1999","unstructured":"Albert, R., Barab\u00e1si, A.-L.: Emergence of scaling in random networks. Science\u00a0286, 509\u2013512 (1999)","journal-title":"Science"},{"issue":"1","key":"16_CR2","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\u00a066(1), 18\u201350 (2013)","journal-title":"Algorithmica"},{"key":"16_CR3","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in \u00f5(n2) time. In: Proc. of 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 271\u2013280 (2004)"},{"issue":"4","key":"16_CR4","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S. Baswana","year":"2006","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expected O(n 2) time. ACM Transactions on Algorithms\u00a02(4), 557\u2013577 (2006)","journal-title":"ACM Transactions on Algorithms"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-642-02011-7_7","volume-title":"Experimental Algorithms","author":"R. Bauer","year":"2009","unstructured":"Bauer, R., Wagner, D.: Batch dynamic single-source shortest-path algorithms: An experimental study. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol.\u00a05526, pp. 51\u201362. Springer, Heidelberg (2009)"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.\u00a08737, pp. 137\u2013148. Springer, Heidelberg (2014)"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B.: Random Graphs. Cambridge University Press (2001)","DOI":"10.1017\/CBO9780511814068"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Chechik, S.: Approximate distance oracles with constant query time. In: Proc. of 46th ACM Symposium on Theory of Computing (STOC), pp. 654\u2013663 (2014)","DOI":"10.1145\/2591796.2591801"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: Proc. of 41st ACM Symposium on Theory of Computing (STOC), pp. 435\u2013444. ACM (2009)","DOI":"10.1145\/1536414.1536475"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-642-15775-2_8","volume-title":"Algorithms \u2013 ESA 2010","author":"S. Chechik","year":"2010","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: f-sensitivity distance oracles and routing schemes. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 84\u201396. Springer, Heidelberg (2010)"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-319-03578-9_24","volume-title":"Structural Information and Communication Complexity","author":"A. D\u2019Andrea","year":"2013","unstructured":"D\u2019Andrea, A., D\u2019Emidio, M., Frigioni, D., Leucci, S., Proietti, G.: Dynamically maintaining shortest path trees under batches of updates. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol.\u00a08179, pp. 286\u2013297. Springer, Heidelberg (2013)"},{"key":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/978-3-319-07959-2_24","volume-title":"Experimental Algorithms","author":"A. D\u2019Andrea","year":"2014","unstructured":"D\u2019Andrea, A., D\u2019Emidio, M., Frigioni, D., Leucci, S., Proietti, G.: Experimental evaluation of dynamic shortest path tree algorithms on homogeneous batches. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol.\u00a08504, pp. 283\u2013294. Springer, Heidelberg (2014)"},{"key":"16_CR13","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory of Graphs and its Applications, pp. 29\u201336 (1964)"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Williams, V.V.: Improved distance sensitivity oracles via fast single-source replacement paths. In: Proc. of 53rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 748\u2013757. IEEE (2012)","DOI":"10.1109\/FOCS.2012.17"},{"issue":"3","key":"16_CR15","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\u00a049(3), 171\u2013191 (2007)","journal-title":"Algorithmica"},{"issue":"2","key":"16_CR16","doi-asserted-by":"crossref","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.\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"key":"16_CR17","unstructured":"Hyun, Y., Huffaker, B., Andersen, D., Aben, E., Shannon, C., Luckie, M., Claffy, K.C.: The CAIDA IPv4 routed\/24 topology dataset. http:\/\/www.caida.org\/data\/active\/ipv4_routed_24_topology_dataset.xml"},{"key":"16_CR18","unstructured":"Ito, H., Iwama, K., Okabe, Y., Yoshihiro, T.: Polynomial-time computable backup tables for shortest-path routing. In: Proc. of 10th Internaltional Colloquium on Structural Information Complexity (SIROCCO). Proceedings in Informatics, vol.\u00a017, pp. 163\u2013177. Carleton Scientific (2003)"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Mereu, A., Cherubini, D., Fanni, A., Frangioni, A.: Primary and backup paths optimal design for traffic engineering in hybrid igp\/mpls networks. In: Proc. of 7th International Workshop on Design of Reliable Communication Networks (DRCN), pp. 273\u2013280. IEEE (2009)","DOI":"10.1109\/DRCN.2009.5339995"},{"issue":"1","key":"16_CR20","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\u00a035(1), 56\u201374 (2003)","journal-title":"Algorithmica"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"Parter, M., Peleg, D.: Fault tolerant approximate BFS structures. In: Proc. of 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1073\u20131092. SIAM (2014)","DOI":"10.1137\/1.9781611973402.80"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/11523468_22","volume-title":"Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"issue":"1","key":"16_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of ACM\u00a052(1), 1\u201324 (2005)","journal-title":"Journal of ACM"}],"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-25258-2_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T13:54:27Z","timestamp":1567259667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25258-2_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319252575","9783319252582"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25258-2_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}