{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T16:08:27Z","timestamp":1775578107971,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642404498","type":"print"},{"value":"9783642404504","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_66","type":"book-chapter","created":{"date-parts":[[2013,8,15]],"date-time":"2013-08-15T23:22:47Z","timestamp":1376608967000},"page":"779-790","source":"Crossref","is-referenced-by-count":12,"title":["Sparse Fault-Tolerant BFS Trees"],"prefix":"10.1007","author":[{"given":"Merav","family":"Parter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"66_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Compact distributed data structures for adaptive network routing. In: STOC, pp. 230\u2013240 (1989)","DOI":"10.1145\/73007.73053"},{"key":"66_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Chechik, S., Gavoille, C., Peleg, D.: Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension. In: PODC, pp. 192\u2013200 (2010)","DOI":"10.1145\/1835698.1835743"},{"issue":"4","key":"66_CR3","doi-asserted-by":"publisher","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\n                2) time. ACM Trans. Algorithms\u00a02(4), 557\u2013577 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"66_CR4","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Karger, D.: A nearly optimal oracle for avoiding failed vertices and edges. In: STOC, pp. 101\u2013110 (2009)","DOI":"10.1145\/1536414.1536431"},{"key":"66_CR5","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: f-sensitivity distance oracles and routing schemes. Algorithmica, 861\u2013882 (2012)","DOI":"10.1007\/s00453-011-9543-0"},{"key":"66_CR6","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: STOC, pp. 435\u2013444 (2009)","DOI":"10.1145\/1536414.1536475"},{"key":"66_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-642-22012-8_7","volume-title":"Automata, Languages and Programming","author":"S. Chechik","year":"2011","unstructured":"Chechik, S.: Fault-Tolerant Compact Routing Schemes for General Graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 101\u2013112. Springer, Heidelberg (2011)"},{"key":"66_CR8","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discrete & Computational Geometry\u00a032 (2003)","DOI":"10.1007\/s00454-004-1121-7"},{"key":"66_CR9","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., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J. Computing\u00a037, 1299\u20131318 (2008)","journal-title":"SIAM J. Computing"},{"key":"66_CR10","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: PODC, pp. 169\u2013178 (2011)","DOI":"10.1145\/1993806.1993830"},{"key":"66_CR11","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Dual-failure distance and connectivity oracles. In: SODA (2009)","DOI":"10.1137\/1.9781611973068.56"},{"key":"66_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U.: A Threshold of ln n for Approximating Set Cover. J. ACM, 634\u2013652 (1998)","DOI":"10.1145\/285055.285059"},{"key":"66_CR13","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Williams, V.V.: Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths. In: FOCS (2012)","DOI":"10.1109\/FOCS.2012.17"},{"key":"66_CR14","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Subhash, S.: Vickrey prices and shortest paths: What is an edge worth? In: FOCS (2001)","DOI":"10.1109\/SFCS.2001.959899"},{"key":"66_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/3-540-36494-3_31","volume-title":"STACS 2003","author":"J. Hershberger","year":"2003","unstructured":"Hershberger, J., Subhash, S., Bhosle, A.: On the difficulty of some shortest path problems. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 343\u2013354. Springer, Heidelberg (2003)"},{"key":"66_CR16","doi-asserted-by":"crossref","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.: Efficient algorithms for constructing fault-tolerant geometric spanners. In: STOC, pp. 186\u2013195 (1998)","DOI":"10.1145\/276698.276734"},{"key":"66_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/3-540-48447-7_20","volume-title":"Algorithms and Data Structures","author":"T. Lukovszki","year":"1999","unstructured":"Lukovszki, T.: New results on fault tolerant geometric spanners. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 193\u2013204. Springer, Heidelberg (1999)"},{"key":"66_CR18","unstructured":"Parter, P., Peleg, D.: Sparse Fault-Tolerant BFS Trees (2013), \n                  \n                    http:\/\/arxiv.org\/abs\/1302.5401"},{"key":"66_CR19","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"66_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"issue":"2","key":"66_CR21","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Computing\u00a018(2), 740\u2013747 (1989)","journal-title":"SIAM J. Computing"},{"key":"66_CR22","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM\u00a036, 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"66_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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)"},{"key":"66_CR24","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algorithms (2012)","DOI":"10.1145\/2344422.2344423"},{"key":"66_CR25","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"key":"66_CR26","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\u00a052, 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"66_CR27","unstructured":"Vazirani, V.: Approximation Algorithms. Georgia Inst. Tech. (1997)"},{"key":"66_CR28","doi-asserted-by":"crossref","unstructured":"Weimann, O., Yuster, R.: Replacement paths via fast matrix multiplication. In: FOCS (2010)","DOI":"10.1109\/FOCS.2010.68"}],"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_66","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T12:57:40Z","timestamp":1558011460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}