{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T04:19:47Z","timestamp":1745381987546,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642348617"},{"type":"electronic","value":"9783642348624"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34862-4_8","type":"book-chapter","created":{"date-parts":[[2012,11,26]],"date-time":"2012-11-26T09:00:11Z","timestamp":1353920411000},"page":"108-119","source":"Crossref","is-referenced-by-count":0,"title":["Multipath Spanners via Fault-Tolerant Spanners"],"prefix":"10.1007","author":[{"given":"Shiri","family":"Chechik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quentin","family":"Godfroy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear cost sequential and distributed constructions of sparse neighborhood covers. In: Proc. 34th IEEE FOCS, pp. 638\u2013647 (1993)","DOI":"10.1109\/SFCS.1993.366823"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. In: Proc. 29th ACM PODC, pp. 410\u2013419 (2010)","DOI":"10.1145\/1835698.1835797"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proc. 47th IEEE FOCS, pp. 591\u2013602 (2006)","DOI":"10.1109\/FOCS.2006.29"},{"key":"8_CR5","unstructured":"Bollob\u00e1s, B., Coppersmith, D., Elkin, M.: Sparse distance preservers and additive spanners. In: Proc. 14th ACM-SIAM SODA, pp. 414\u2013423 (2003)"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: Proc. 41st ACM STOC, pp. 435\u2013444 (2009)","DOI":"10.1145\/1536414.1536475"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L. Cowen","year":"2001","unstructured":"Cowen, L.: Compact routing with minimum stretch. J. Algo.\u00a038, 170\u2013183 (2001)","journal-title":"J. Algo."},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jalgor.2003.08.001","volume":"50","author":"L. Cowen","year":"2004","unstructured":"Cowen, L., Wagner, C.: Compact roundtrip routing in directed networks. J. Algo.\u00a050, 79\u201395 (2004)","journal-title":"J. Algo."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-Tolerant Spanners: Better and Simpler. In: Proc. 30th ACM PODC, pp. 169\u2013178 (2011)","DOI":"10.1145\/1993806.1993830"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1016\/j.jcss.2005.04.002","volume":"71","author":"D. Dubhashi","year":"2005","unstructured":"Dubhashi, D., Mei, A., Panconesi, A., Radhakrishnan, J., Srinivasan, A.: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J. Computer and System Sciences\u00a071, 467\u2013479 (2005)","journal-title":"J. Computer and System Sciences"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Tr. Algo.\u00a01, 283\u2013323 (2005)","journal-title":"ACM Tr. Algo."},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Elkin, M.: A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In: Proc. 26th ACM PODC, pp. 185\u2013194 (2007)","DOI":"10.1145\/1281100.1281128"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Elkin, M., Zhang, J.: Efficient algorithms for constructing (1\u2009+\u2009\u03b5,\u03b2)-spanners in the distributed and streaming models. In: Proc. 23rd ACM PODC, pp. 160\u2013168 (2004)","DOI":"10.1145\/1011767.1011791"},{"issue":"2","key":"8_CR14","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0166-218X(03)00259-2","volume":"137","author":"A.M. Farley","year":"2004","unstructured":"Farley, A.M., Proskurowski, A., Zappala, D., Windisch, K.: Spanners and message distribution in networks. Discrete Applied Mathematics\u00a0137(2), 159\u2013171 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-642-13284-1_17","volume-title":"Structural Information and Communication Complexity","author":"C. Gavoille","year":"2010","unstructured":"Gavoille, C., Godfroy, Q., Viennot, L.: Multipath Spanners. In: Patt-Shamir, B., Ekim, T. (eds.) SIROCCO 2010. LNCS, vol.\u00a06058, pp. 211\u2013223. Springer, Heidelberg (2010)"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-642-25873-2_11","volume-title":"Principles of Distributed Systems","author":"C. Gavoille","year":"2011","unstructured":"Gavoille, C., Godfroy, Q., Viennot, L.: Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners. In: Fern\u00e0ndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol.\u00a07109, pp. 143\u2013158. Springer, Heidelberg (2011)"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Jacquet, P., Viennot, L.: Remote spanners: what to know beyond neighbors. In: Proc. 23rd IEEE IPDPS (2009)","DOI":"10.1109\/IPDPS.2009.5161041"},{"key":"8_CR18","unstructured":"Kushman, N., Kandula, S., Katabi, D., Maggs, B.M.: R-BGP: Staying connected in a connected world. In: Proc. 4th NSDI (2007)"},{"key":"8_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-540-24663-3_10","volume-title":"Performance Tools and Applications to Networked Systems","author":"S. Mueller","year":"2004","unstructured":"Mueller, S., Tsang, R.P., Ghosal, D.: Multipath Routing in Mobile Ad Hoc Networks: Issues and Challenges. In: Calzarossa, M.C., Gelenbe, E. (eds.) MASCOTS 2003. LNCS, vol.\u00a02965, pp. 209\u2013234. Springer, Heidelberg (2004)"},{"issue":"4","key":"8_CR20","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1023\/A:1011426611520","volume":"6","author":"A. Nasipuri","year":"2001","unstructured":"Nasipuri, A., Casta\u00f1eda, R., Das, S.R.: Performance of multipath routing for on-demand protocols in mobile ad hoc networks. Mobile Networks and Applications\u00a06(4), 339\u2013349 (2001)","journal-title":"Mobile Networks and Applications"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Peleg, D., Sch\u00e1ffer, A.A.: Graph spanners. J. Graph Theory, 99\u2013116 (1989)","DOI":"10.1002\/jgt.3190130114"},{"issue":"4","key":"8_CR22","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(4), 740\u2013747 (1989)","journal-title":"SIAM J. Computing"},{"key":"8_CR23","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_CR24","doi-asserted-by":"crossref","unstructured":"Pan, P., Swallow, G., Atlas, A.: Fast Reroute Extensions to RSVP-TE for LSP Tunnels. RFC 4090 (Proposed Standard) (2005)","DOI":"10.17487\/rfc4090"},{"issue":"4","key":"8_CR25","first-page":"29","volume":"3","author":"L. Roditty","year":"2008","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms 3(4), Article 29 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"8_CR26","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proc. SPAA, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"key":"8_CR27","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. JACM\u00a052, 1\u201324 (2005)","journal-title":"JACM"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: Lower bounds for additive spanners, emulators, and more. In: Proc. 47th IEEE FOCS, pp. 389\u2013398 (2006)","DOI":"10.1109\/FOCS.2006.45"}],"container-title":["Lecture Notes in Computer Science","Design and Analysis of Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34862-4_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T20:38:44Z","timestamp":1745354324000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34862-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642348617","9783642348624"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34862-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}