{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T21:56:49Z","timestamp":1718920609751},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,6,23]],"date-time":"2011-06-23T00:00:00Z","timestamp":1308787200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00453-011-9543-0","type":"journal-article","created":{"date-parts":[[2011,6,22]],"date-time":"2011-06-22T10:12:22Z","timestamp":1308737542000},"page":"861-882","source":"Crossref","is-referenced-by-count":29,"title":["f-Sensitivity Distance Oracles and Routing Schemes"],"prefix":"10.1007","volume":"63","author":[{"given":"Shiri","family":"Chechik","sequence":"first","affiliation":[]},{"given":"Michael","family":"Langberg","sequence":"additional","affiliation":[]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,6,23]]},"reference":[{"key":"9543_CR1","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1145\/195613.195651","volume":"41","author":"Y. Afek","year":"1994","unstructured":"Afek, Y., Attiya, H., Fekete, A., Fischer, M.J., Lynch, N., Mansour, Y., Wang, D., Zuck, L.D.: Reliable communication over unreliable channels. J. ACM 41, 1267\u20131297 (1994)","journal-title":"J. ACM"},{"key":"9543_CR2","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1006\/jagm.1996.0819","volume":"22","author":"Y. Afek","year":"1997","unstructured":"Afek, Y., Awerbuch, B., Gafni, E., Mansour, Y., Rosen, A., Shavit, N.: Slide-the key to polynomial end-to-end communication. J. Algorithms 22, 158\u2013186 (1997)","journal-title":"J. Algorithms"},{"issue":"4","key":"9543_CR3","doi-asserted-by":"crossref","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. Comput. 28(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"9543_CR4","first-page":"278","volume-title":"Proc. 3rd ACM Symp. on Principles of Distributed Computing (PODC)","author":"B. Awerbuch","year":"1984","unstructured":"Awerbuch, B., Even, S.: Efficient and reliable broadcast is achievable in an eventually connected network. In: Proc. 3rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 278\u2013281 (1984)"},{"key":"9543_CR5","first-page":"503","volume-title":"Proc. 31st IEEE Symp. on Foundations of Computer Science","author":"B. Awerbuch","year":"1990","unstructured":"Awerbuch, B., Peleg, D.: Sparse partitions. In: Proc. 31st IEEE Symp. on Foundations of Computer Science, pp. 503\u2013513 (1990)"},{"key":"9543_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Improved routing strategies with succinct tables. J.\u00a0Algorithms 307\u2013341 (1990)","DOI":"10.1016\/0196-6774(90)90017-9"},{"key":"9543_CR7","first-page":"410","volume-title":"Proc. INFOCOM","author":"B. Awerbuch","year":"1991","unstructured":"Awerbuch, B., Kutten, S., Peleg, D.: On buffer-economical store-and-forward deadlock prevention. In: Proc. INFOCOM, pp. 410\u2013414 (1991)"},{"key":"9543_CR8","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1109\/12.286303","volume":"43","author":"A. Bagchi","year":"1994","unstructured":"Bagchi, A., Hakimi, S.L.: Information dissemination in distributed systems with faulty units. IEEE Trans. Comput. 43, 698\u2013710 (1994)","journal-title":"IEEE Trans. Comput."},{"key":"9543_CR9","first-page":"215","volume-title":"Proc. WDAG\u201995","author":"F. Bao","year":"1995","unstructured":"Bao, F., Igarashi, Y., Katano, K.: Broadcasting in hypercubes with randomly distributed byzantine faults. In: Proc. WDAG\u201995, pp. 215\u2013229 (1995)"},{"key":"9543_CR10","first-page":"591","volume-title":"Proc. IEEE Symp. on Foundations of Computer Science","author":"S. Baswana","year":"2006","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proc. IEEE Symp. on Foundations of Computer Science, pp. 591\u2013602 (2006)"},{"key":"9543_CR11","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1007\/3-540-45061-0_32","volume-title":"Proc. 30th Int. Colloq. on Automata, Languages and Programming","author":"S. Baswana","year":"2003","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing sparse spanners in weighted graphs. In: Proc. 30th Int. Colloq. on Automata, Languages and Programming, pp. 384\u2013396 (2003)"},{"issue":"4","key":"9543_CR12","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 Trans. Algorithms 2(4), 557\u2013577 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"9543_CR13","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1006\/jagm.1996.0810","volume":"22","author":"P. Berman","year":"1997","unstructured":"Berman, P., Diks, K., Pelc, A.: Reliable broadcasting in logarithmic time with byzantine link failures. J. Algorithms 22, 199\u2013211 (1997)","journal-title":"J. Algorithms"},{"key":"9543_CR14","first-page":"34","volume-title":"Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA)","author":"A. Bernstein","year":"2008","unstructured":"Bernstein, A., Karger, D.: Improved distance sensitivity oracles via random sampling. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 34\u201343 (2008)"},{"key":"9543_CR15","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1145\/1536414.1536431","volume-title":"Proc. 41st ACM Symp. on Theory of Computing (STOC)","author":"A. Bernstein","year":"2009","unstructured":"Bernstein, A., Karger, D.: A nearly optimal oracle for avoiding failed vertices and edges. In: Proc. 41st ACM Symp. on Theory of Computing (STOC), pp. 101\u2013110 (2009)"},{"key":"9543_CR16","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1002\/net.3230230807","volume":"23","author":"D. Blough","year":"1993","unstructured":"Blough, D., Pelc, A.: Optimal communication in networks with randomly distributed byzantine faults. Networks 23, 691\u2013701 (1993)","journal-title":"Networks"},{"issue":"7","key":"9543_CR17","doi-asserted-by":"crossref","first-page":"3403","DOI":"10.1137\/090758039","volume":"37","author":"S. Chechik","year":"2010","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. SIAM J. Comput. 37(7), 3403\u20133423 (2010)","journal-title":"SIAM J. Comput."},{"key":"9543_CR18","first-page":"648","volume-title":"Proc. IEEE Symp. on Foundations of Computer Science","author":"E. Cohen","year":"1993","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. In: Proc. IEEE Symp. on Foundations of Computer Science, pp. 648\u2013658 (1993)"},{"key":"9543_CR19","first-page":"37","volume-title":"Proc. STACS","author":"B. Courcelle","year":"2007","unstructured":"Courcelle, B., Twigg, A.: Compact forbidden-set routing. In: Proc. STACS, pp. 37\u201348 (2007)"},{"key":"9543_CR20","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L.J. Cowen","year":"2001","unstructured":"Cowen, L.J.: Compact routing with minimum stretch. J. Algorithms 38, 170\u2013183 (2001)","journal-title":"J. Algorithms"},{"key":"9543_CR21","first-page":"362","volume-title":"Proc. 15th SODA","author":"C. Demetrescu","year":"2004","unstructured":"Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. In: Proc. 15th SODA, pp. 362\u2013371 (2004)"},{"issue":"5","key":"9543_CR22","doi-asserted-by":"crossref","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. Comput. 37(5), 1299\u20131318 (2008)","journal-title":"SIAM J. Comput."},{"key":"9543_CR23","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0405025","volume":"5","author":"K. Diks","year":"1992","unstructured":"Diks, K., Pelc, A.: Almost safe gossiping in bounded degree networks. SIAM J. Discrete Math. 5, 338\u2013344 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9543_CR24","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0196-6774(82)90004-9","volume":"3","author":"D. Dolev","year":"1982","unstructured":"Dolev, D.: The byzantine generals strike again. J. Algorithms 3, 14\u201330 (1982)","journal-title":"J. Algorithms"},{"issue":"5","key":"9543_CR25","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"key":"9543_CR26","volume-title":"Proc. SODA","author":"R. Duan","year":"2009","unstructured":"Duan, R., Pettie, S.: Dual-failure distance and connectivity oracles. In: Proc. SODA (2009)"},{"key":"9543_CR27","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0196-6774(03)00002-6","volume":"46","author":"T. Eilam","year":"2003","unstructured":"Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. J. Algorithms 46, 97\u2013114 (2003)","journal-title":"J. Algorithms"},{"issue":"2","key":"9543_CR28","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Trans. Algorithms 1(2), 283\u2013323 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"9543_CR29","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, N.: Sparsification\u2014A technique for speeding up dynamic graph algorithms. J. ACM 44 (1997)","DOI":"10.1145\/265910.265914"},{"key":"9543_CR30","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1145\/174147.169676","volume":"40","author":"A.D. Fekete","year":"1993","unstructured":"Fekete, A.D., Lynch, N., Mansour, Y., Spinelli, J.: The impossibility of implementing reliable communication in the face of crashes. J. ACM 40, 1087\u20131107 (1993)","journal-title":"J. ACM"},{"key":"9543_CR31","first-page":"223","volume-title":"Proc. 14th ACM Symp. on Principles of Distributed Computing","author":"P. Fraigniaud","year":"1995","unstructured":"Fraigniaud, P., Gavoille, C.: Memory requirement for universal routing schemes. In: Proc. 14th ACM Symp. on Principles of Distributed Computing, pp. 223\u2013230 (1995)"},{"key":"9543_CR32","first-page":"131","volume-title":"Proc. 7th ACM Symp. on Principles of Distributed Computing (PODC)","author":"E. Gafni","year":"1988","unstructured":"Gafni, E., Afek, Y.: End-to-end communication in unreliable networks. In: Proc. 7th ACM Symp. on Principles of Distributed Computing (PODC), pp. 131\u2013148 (1988)"},{"key":"9543_CR33","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1006\/jpdc.2000.1705","volume":"61","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Gengler, M.: Space-efficiency for routing schemes of stretch factor three. J. Parallel Distrib. Comput. 61, 679\u2013687 (2001)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9543_CR34","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C. Gavoille","year":"2003","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16, 111\u2013120 (2003)","journal-title":"Distrib. Comput."},{"key":"9543_CR35","first-page":"85","volume-title":"Proc 7th ACM Symp. on Principles of Distributed Computing (PODC)","author":"O. Goldreich","year":"1989","unstructured":"Goldreich, O., Herzberg, A., Mansour, Y.: Source to destination communication in the presence of faults. In: Proc 7th ACM Symp. on Principles of Distributed Computing (PODC), pp. 85\u2013101 (1989)"},{"key":"9543_CR36","first-page":"339","volume-title":"Proc. 8th ACM Symp. on Principles of Distributed Computing (PODC)","author":"A. Herzberg","year":"1989","unstructured":"Herzberg, A., Kutten, S.: Fast isolation of arbitrary forwarding faults. In: Proc. 8th ACM Symp. on Principles of Distributed Computing (PODC), pp. 339\u2013353 (1989)"},{"issue":"4","key":"9543_CR37","doi-asserted-by":"crossref","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"9543_CR38","first-page":"328","volume-title":"Proc. FSTTCS","author":"T. Kavitha","year":"2007","unstructured":"Kavitha, T.: Faster algorithms for all-pairs small stretch distances in weighted graphs. In: Proc. FSTTCS, pp. 328\u2013339 (2007)"},{"key":"9543_CR39","volume-title":"Proc. STACS","author":"N. Khanna","year":"2010","unstructured":"Khanna, N., Baswana, S.: Approximate shortest paths oracle handling single vertex failure. In: Proc. STACS (2010)"},{"key":"9543_CR40","unstructured":"Ku\u010dera, L.: Broadcasting through a noisy one-dimensional network. Technical Report MPI-I-93-106, Max-Planck-Institut, Saarbruecken, Germany (1993)"},{"key":"9543_CR41","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/BF01758778","volume":"7","author":"H. Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica 7, 583\u2013596 (1992)","journal-title":"Algorithmica"},{"key":"9543_CR42","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1109\/FOCS.2007.59","volume-title":"Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"M. P\u01cetra\u015fcu","year":"2007","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Planning for fast connectivity updates. In: Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 263\u2013271 (2007)"},{"key":"9543_CR43","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<143::AID-NET3>3.0.CO;2-N","volume":"28","author":"A. Pelc","year":"1996","unstructured":"Pelc, A.: Fault-tolerant broadcasting and gossiping in communication networks. Networks 28, 143\u2013156 (1996)","journal-title":"Networks"},{"key":"9543_CR44","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/j.tcs.2006.10.031","volume":"370","author":"A. Pelc","year":"2007","unstructured":"Pelc, A., Peleg, D.: Feasibility and complexity of broadcasting with random transmission failures. Theor. Comput. Sci. 370, 279\u2013292 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9543_CR45","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"issue":"4","key":"9543_CR46","doi-asserted-by":"crossref","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. Comput. 18(4), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9543_CR47","doi-asserted-by":"crossref","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 36(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"9543_CR48","first-page":"184","volume-title":"Proc. 36th STOC","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proc. 36th STOC, pp. 184\u2013191 (2004)"},{"key":"9543_CR49","first-page":"261","volume-title":"Proc. 32nd ICALP","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Proc. 32nd ICALP, pp. 261\u2013272 (2005)"},{"issue":"3","key":"9543_CR50","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1367064.1367069","volume":"4","author":"L. Roditty","year":"2008","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms 4(3), 1\u201317 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"9543_CR51","first-page":"384","volume-title":"Proc. 9th SWAT","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Proc. 9th SWAT, pp. 384\u2013396 (2004)"},{"key":"9543_CR52","first-page":"112","volume-title":"Proc. 37th ACM Symp. on Theory of Computing (STOC)","author":"M. Thorup","year":"2005","unstructured":"Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: Proc. 37th ACM Symp. on Theory of Computing (STOC), pp. 112\u2013119 (2005)"},{"key":"9543_CR53","first-page":"1","volume-title":"Proc. 13th ACM Symp. on Parallel Algorithms and Architectures (SPAA)","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proc. 13th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 1\u201310 (2001)"},{"issue":"1","key":"9543_CR54","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. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"9543_CR55","unstructured":"Thurimella, R.: Techniques for the design of parallel graph algorithms. PhD thesis, Univ. of Texas, Austin (1989)"},{"key":"9543_CR56","unstructured":"Twigg, A.: Compact forbidden-set routing. PhD thesis, Cambridge University (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9543-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9543-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9543-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:05:19Z","timestamp":1560297919000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9543-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,23]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9543"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9543-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,23]]}}}