Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

f-Sensitivity Distance Oracles and Routing Schemes

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Anf-sensitivity distance oracle for a weighted undirected graphG(V,E) is a data structure capable of answering restricted distance queries between vertex pairs, i.e., calculating distances on a subgraph avoiding some forbidden edges. This paper presents an efficiently constructiblef-sensitivity distance oracle that given a triplet (s,t,F), wheres andt are vertices andF is a set of forbidden edges such that |F|≤f, returns an estimate of the distance betweens andt inG(V,E∖F). For an integer parameterk≥1, the size of the data structure isO(fkn1+1/klog (nW)), whereW is the heaviest edge inG, the stretch (approximation ratio) of the returned distance is (8k−2)(f+1), and the query time isO(|F|⋅log 2n⋅log log n⋅log log d), whered is the distance betweens andt inG(V,E∖F).

Our result differs from previous ones in two major respects: (1) it is the first to considerapproximate oracles for general graphs (and thus obtain a succinct data structure); (2) our result holds for an arbitrary number of forbidden edges. In contrast, previous papers concernf-sensitiveexact distance oracles, which consequently have size Ω(n2). Moreover, those oracles support forbidden setsF of size |F|≤2.

The paper also considersf-sensitive compact routing schemes, namely, routing schemes that avoid a given set of forbidden (orfailed) edges. It presents a scheme capable of withstanding up to two edge failures. Given a messageM destined tot at a source vertexs, in the presence of a forbidden edge setF of size |F|≤2 (unknown tos), our scheme routesM froms tot in a distributed manner, over a path of length at mostO(k) times the length of the optimal path (avoidingF). The total amount of information stored in vertices ofG isO(kn1+1/klog (nW)log n). To the best of our knowledge, this is the first result obtaining anf-sensitive compact routing scheme for general graphs.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Afek, Y., Attiya, H., Fekete, A., Fischer, M.J., Lynch, N., Mansour, Y., Wang, D., Zuck, L.D.: Reliable communication over unreliable channels. J. ACM41, 1267–1297 (1994)

    Article MathSciNet  Google Scholar 

  2. Afek, Y., Awerbuch, B., Gafni, E., Mansour, Y., Rosen, A., Shavit, N.: Slide-the key to polynomial end-to-end communication. J. Algorithms22, 158–186 (1997)

    Article MathSciNet MATH  Google Scholar 

  3. Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput.28(4), 1167–1181 (1999)

    Article MathSciNet MATH  Google Scholar 

  4. 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–281 (1984)

    Chapter  Google Scholar 

  5. Awerbuch, B., Peleg, D.: Sparse partitions. In: Proc. 31st IEEE Symp. on Foundations of Computer Science, pp. 503–513 (1990)

    Google Scholar 

  6. Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Improved routing strategies with succinct tables. J. Algorithms 307–341 (1990)

  7. Awerbuch, B., Kutten, S., Peleg, D.: On buffer-economical store-and-forward deadlock prevention. In: Proc. INFOCOM, pp. 410–414 (1991)

    Google Scholar 

  8. Bagchi, A., Hakimi, S.L.: Information dissemination in distributed systems with faulty units. IEEE Trans. Comput.43, 698–710 (1994)

    Article MATH  Google Scholar 

  9. Bao, F., Igarashi, Y., Katano, K.: Broadcasting in hypercubes with randomly distributed byzantine faults. In: Proc. WDAG’95, pp. 215–229 (1995)

    Google Scholar 

  10. 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–602 (2006)

    Google Scholar 

  11. 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–396 (2003)

    Chapter  Google Scholar 

  12. Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expectedO(n2) time. ACM Trans. Algorithms2(4), 557–577 (2006)

    Article MathSciNet  Google Scholar 

  13. Berman, P., Diks, K., Pelc, A.: Reliable broadcasting in logarithmic time with byzantine link failures. J. Algorithms22, 199–211 (1997)

    Article MathSciNet MATH  Google Scholar 

  14. Bernstein, A., Karger, D.: Improved distance sensitivity oracles via random sampling. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 34–43 (2008)

    Google Scholar 

  15. 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–110 (2009)

    Chapter  Google Scholar 

  16. Blough, D., Pelc, A.: Optimal communication in networks with randomly distributed byzantine faults. Networks23, 691–701 (1993)

    Article MathSciNet MATH  Google Scholar 

  17. Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. SIAM J. Comput.37(7), 3403–3423 (2010)

    Article MathSciNet  Google Scholar 

  18. Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. In: Proc. IEEE Symp. on Foundations of Computer Science, pp. 648–658 (1993)

    Google Scholar 

  19. Courcelle, B., Twigg, A.: Compact forbidden-set routing. In: Proc. STACS, pp. 37–48 (2007)

    Google Scholar 

  20. Cowen, L.J.: Compact routing with minimum stretch. J. Algorithms38, 170–183 (2001)

    Article MathSciNet MATH  Google Scholar 

  21. Demetrescu, C., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. In: Proc. 15th SODA, pp. 362–371 (2004)

    Google Scholar 

  22. Demetrescu, C., Thorup, M., Chowdhury, R., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J. Comput.37(5), 1299–1318 (2008)

    Article MathSciNet MATH  Google Scholar 

  23. Diks, K., Pelc, A.: Almost safe gossiping in bounded degree networks. SIAM J. Discrete Math.5, 338–344 (1992)

    Article MathSciNet MATH  Google Scholar 

  24. Dolev, D.: The byzantine generals strike again. J. Algorithms3, 14–30 (1982)

    Article MathSciNet MATH  Google Scholar 

  25. Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput.29(5), 1740–1759 (2000)

    Article MathSciNet MATH  Google Scholar 

  26. Duan, R., Pettie, S.: Dual-failure distance and connectivity oracles. In: Proc. SODA (2009)

    Google Scholar 

  27. Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. J. Algorithms46, 97–114 (2003)

    Article MathSciNet MATH  Google Scholar 

  28. Elkin, M.: Computing almost shortest paths. ACM Trans. Algorithms1(2), 283–323 (2005)

    Article MathSciNet  Google Scholar 

  29. Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, N.: Sparsification—A technique for speeding up dynamic graph algorithms. J. ACM44 (1997)

  30. Fekete, A.D., Lynch, N., Mansour, Y., Spinelli, J.: The impossibility of implementing reliable communication in the face of crashes. J. ACM40, 1087–1107 (1993)

    Article MathSciNet MATH  Google Scholar 

  31. Fraigniaud, P., Gavoille, C.: Memory requirement for universal routing schemes. In: Proc. 14th ACM Symp. on Principles of Distributed Computing, pp. 223–230 (1995)

    Google Scholar 

  32. Gafni, E., Afek, Y.: End-to-end communication in unreliable networks. In: Proc. 7th ACM Symp. on Principles of Distributed Computing (PODC), pp. 131–148 (1988)

    Chapter  Google Scholar 

  33. Gavoille, C., Gengler, M.: Space-efficiency for routing schemes of stretch factor three. J. Parallel Distrib. Comput.61, 679–687 (2001)

    Article MATH  Google Scholar 

  34. Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput.16, 111–120 (2003)

    Article  Google Scholar 

  35. 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–101 (1989)

    Google Scholar 

  36. Herzberg, A., Kutten, S.: Fast isolation of arbitrary forwarding faults. In: Proc. 8th ACM Symp. on Principles of Distributed Computing (PODC), pp. 339–353 (1989)

    Chapter  Google Scholar 

  37. Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM48(4), 723–760 (2001)

    Article MathSciNet MATH  Google Scholar 

  38. Kavitha, T.: Faster algorithms for all-pairs small stretch distances in weighted graphs. In: Proc. FSTTCS, pp. 328–339 (2007)

    Google Scholar 

  39. Khanna, N., Baswana, S.: Approximate shortest paths oracle handling single vertex failure. In: Proc. STACS (2010)

    Google Scholar 

  40. Kučera, L.: Broadcasting through a noisy one-dimensional network. Technical Report MPI-I-93-106, Max-Planck-Institut, Saarbruecken, Germany (1993)

  41. Nagamochi, H., Ibaraki, T.: Linear time algorithms for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica7, 583–596 (1992)

    Article MathSciNet MATH  Google Scholar 

  42. Pǎtraşcu, M., Thorup, M.: Planning for fast connectivity updates. In: Proc. 48th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 263–271 (2007)

    Google Scholar 

  43. Pelc, A.: Fault-tolerant broadcasting and gossiping in communication networks. Networks28, 143–156 (1996)

    Article MathSciNet MATH  Google Scholar 

  44. Pelc, A., Peleg, D.: Feasibility and complexity of broadcasting with random transmission failures. Theor. Comput. Sci.370, 279–292 (2007)

    Article MathSciNet MATH  Google Scholar 

  45. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)

    Book MATH  Google Scholar 

  46. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput.18(4), 740–747 (1989)

    Article MathSciNet MATH  Google Scholar 

  47. Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM36(3), 510–530 (1989)

    Article MathSciNet MATH  Google Scholar 

  48. Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proc. 36th STOC, pp. 184–191 (2004)

    Google Scholar 

  49. Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Proc. 32nd ICALP, pp. 261–272 (2005)

    Google Scholar 

  50. Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms4(3), 1–17 (2008)

    Article MathSciNet  Google Scholar 

  51. Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Proc. 9th SWAT, pp. 384–396 (2004)

    Google Scholar 

  52. 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–119 (2005)

    Google Scholar 

  53. Thorup, M., Zwick, U.: Compact routing schemes. In: Proc. 13th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 1–10 (2001)

    Google Scholar 

  54. Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM52(1), 1–24 (2005)

    Article MathSciNet MATH  Google Scholar 

  55. Thurimella, R.: Techniques for the design of parallel graph algorithms. PhD thesis, Univ. of Texas, Austin (1989)

  56. Twigg, A.: Compact forbidden-set routing. PhD thesis, Cambridge University (2006)

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science and Applied Math., The Weizmann Institute, Rehovot, Israel

    Shiri Chechik & David Peleg

  2. Computer Science Division, Open University of Israel, Raanana, Israel

    Michael Langberg

  3. Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel

    Liam Roditty

Authors
  1. Shiri Chechik

    You can also search for this author inPubMed Google Scholar

  2. Michael Langberg

    You can also search for this author inPubMed Google Scholar

  3. David Peleg

    You can also search for this author inPubMed Google Scholar

  4. Liam Roditty

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toDavid Peleg.

Additional information

The work of the second author was supported in part by The Open University of Israel’s Research Fund (grant no. 46109) and Cisco Collaborative Research Initiative (CCRI).

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp