{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:31:04Z","timestamp":1725557464990},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642132834"},{"type":"electronic","value":"9783642132841"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13284-1_17","type":"book-chapter","created":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T07:43:53Z","timestamp":1275723833000},"page":"211-223","source":"Crossref","is-referenced-by-count":2,"title":["Multipath Spanners"],"prefix":"10.1007","author":[{"given":"Cyril","family":"Gavoille","sequence":"first","affiliation":[]},{"given":"Quentin","family":"Godfroy","sequence":"additional","affiliation":[]},{"given":"Laurent","family":"Viennot","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_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. on Computing\u00a028, 1167\u20131181 (1999)","journal-title":"SIAM J. on Computing"},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s003730200002","volume":"18","author":"N. Alon","year":"2002","unstructured":"Alon, N., Hoory, S., Linial, N.: The Moore bound for irregular graphs. Graphs and Combinatorics\u00a018, 53\u201357 (2002)","journal-title":"Graphs and Combinatorics"},{"key":"17_CR3","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.A., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"17_CR4","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (\u03b1,\u03b2)-spanners and purely additive spanners. In: 16th Symposium on Discrete Algorithms (SODA), January 2005, pp. 672\u2013681. ACM-SIAM (2005)"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/1536414.1536475","volume-title":"41stAnnual ACM Symposium on Theory of Computing (STOC)","author":"S. Chechik","year":"2009","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: 41stAnnual ACM Symposium on Theory of Computing (STOC), May 2009, pp. 435\u2013444. ACM Press, New York (2009)"},{"key":"17_CR6","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/343477.343516","volume-title":"19th Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"L.J. Cowen","year":"2000","unstructured":"Cowen, L.J., Wagner, C.: Compact roundtrip routing in directed networks. In: 19th Annual ACM Symposium on Principles of Distributed Computing (PODC), July 2000, pp. 51\u201359. ACM Press, New York (2000)"},{"key":"17_CR7","first-page":"273","volume-title":"27th Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"B. Derbel","year":"2008","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: On the locality of distributed sparse spanner construction. In: 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), August 2008, pp. 273\u2013282. ACM Press, New York (2008)"},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-04355-0_20","volume-title":"Distributed Computing","author":"B. Derbel","year":"2009","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: Local computation of nearly additive spanners. In: Keidar, I. (ed.) DISC 2009. LNCS, vol.\u00a05805, pp. 176\u2013190. Springer, Heidelberg (2009)"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/11682462_39","volume-title":"LATIN 2006: Theoretical Informatics","author":"F.F. Dragan","year":"2006","unstructured":"Dragan, F.F., Yan, C.: Network flow spanners. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 410\u2013422. Springer, Heidelberg (2006)"},{"key":"17_CR10","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 Transactions on Algorithms\u00a01, 283\u2013323 (2005)","journal-title":"ACM Transactions on Algorithms"},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M. Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: (1\u2009+\u2009\u03b5,\u03b2)-spanner constructions for general graphs. SIAM J. on Computing\u00a033, 608\u2013631 (2004)","journal-title":"SIAM J. on Computing"},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00446-005-0147-2","volume":"18","author":"M. Elkin","year":"2006","unstructured":"Elkin, M., Zhang, J.: Efficient algorithms for constructing (1\u2009+\u2009\u03b5,\u03b2)-spanners in the distributed and streaming models. Distributed Computing\u00a018, 375\u2013385 (2006)","journal-title":"Distributed Computing"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Erd\u00f6s, P.: Extremal problems in graph theory. In: Publ. House Cszechoslovak Acad. Sci., Prague, pp. 29\u201336 (1964)","DOI":"10.4064\/cm-13-2-251-254"},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02579234","volume":"2","author":"P. Erd\u00f6s","year":"1982","unstructured":"Erd\u00f6s, P., Simonovits, M.: Compactness results in extremal graph theory. Combinatorica\u00a02, 275\u2013288 (1982)","journal-title":"Combinatorica"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Gallager, R.G.: A minimum delay routing algorithm using distributed computation. IEEE Transactions on Communications (1977)","DOI":"10.1109\/TCOM.1977.1093711"},{"key":"17_CR16","volume-title":"23rd IEEE International Parallel & Distributed Processing Symposium (IPDPS)","author":"P. Jacquet","year":"2009","unstructured":"Jacquet, P., Viennot, L.: Remote spanners: what to know beyond neighbors. In: 23rd IEEE International Parallel & Distributed Processing Symposium (IPDPS), May 2009. IEEE Computer Society Press, Los Alamitos (2009)"},{"key":"17_CR17","unstructured":"Kleinberg, J.: Approximation algorithms for disjoint paths problems, PhD thesis, Massachusetts Institute of Technology (1996)"},{"key":"17_CR18","unstructured":"Kushman, N., Kandula, S., Katabi, D., Maggs, B.M.: R-bgp: Staying connected in a connected world. In: 4th Symposium on Networked Systems Design and Implementation, NSDI (2007)"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Lee, S., Gerla, M.: Split multipath routing with maximally disjoint paths in ad hoc networks. In: IEEE International Conference on Communications (ICC), vol.\u00a010, pp. 3201\u20133205 (2001)","DOI":"10.1109\/ICC.2001.937262"},{"key":"17_CR20","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1145\/276698.276734","volume-title":"30th Annual ACM Symposium on Theory of Computing (STOC)","author":"C. Levcopoulos","year":"1998","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.: Efficient algorithms for constructing fault-tolerant geometric spanners. In: 30th Annual ACM Symposium on Theory of Computing (STOC), May 1998, pp. 186\u2013195. ACM Press, New York (1998)"},{"key":"17_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/978-3-540-24663-3_10","volume-title":"Performance Tools and Applications to Networked Systems, Revised Tutorial Lectures [from MASCOTS 2003]","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)"},{"key":"17_CR22","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, 339\u2013349 (2001)","journal-title":"Mobile Networks and Applications"},{"key":"17_CR23","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"},{"key":"17_CR24","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. of Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"J. of Graph Theory"},{"key":"17_CR25","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 synchornizer for the hypercube. SIAM J. on Computing\u00a018, 740\u2013747 (1989)","journal-title":"SIAM J. on Computing"},{"key":"17_CR26","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":"17_CR27","first-page":"253","volume-title":"27th Annual ACM Symposium on Principles of Distributed Computing (PODC)","author":"S. Pettie","year":"2008","unstructured":"Pettie, S.: Distributed algorithms for ultrasparse spanners and linear size skeletons. In: 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), August 2008, pp. 253\u2013262. ACM Press, New York (2008)"},{"key":"17_CR28","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 Transactions on Algorithms\u00a03, 29 (2008)","journal-title":"ACM Transactions on Algorithms"},{"key":"17_CR29","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1002\/net.3230140209","volume":"14","author":"J.W. Suurballe","year":"1984","unstructured":"Suurballe, J.W., Tarjan, R.E.: A quick method for finding shortest pairs of disjoint paths. Networks\u00a014, 325\u2013336 (1984)","journal-title":"Networks"},{"key":"17_CR30","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. of the ACM\u00a052, 1\u201324 (2005)","journal-title":"J. of the ACM"},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: 17th Symposium on Discrete Algorithms (SODA), January 2006, pp. 802\u2013809. ACM-SIAM (2006)","DOI":"10.1145\/1109557.1109645"},{"key":"17_CR32","doi-asserted-by":"crossref","unstructured":"Vutukury, S., Garcia-Luna-Aceves, J.J.: A simple approximation to minimum-delay routing. In: SIGCOMM, pp. 227\u2013238 (1999)","DOI":"10.21236\/ADA461850"}],"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-642-13284-1_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T12:41:20Z","timestamp":1685623280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13284-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642132834","9783642132841"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13284-1_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}