Advertisement

Fast Deterministic Distributed Algorithms for Sparse Spanners

  • Bilel Derbel
  • Cyril Gavoille
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)

Abstract

This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with n nodes. All previous deterministic distributed algorithms, for constant stretch spanner of o(n 2) edges, have a running time Ω(n ε ) for some constant ε> 0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of o(n 2) edges in o(n ε ) time for any constant ε> 0.

More precisely, in the Linial’s free model, we construct in \(n^{O(1/\sqrt{\log n})}\) time, for every graph, a 5-spanner of O(n 3/2) edges. The result is extended to O( k2.322)-spanners with O(n 1 + 1/k) edges for every parameter k ≥1. If the minimum degree of the graph is \(\Omega(\sqrt{n})\), then, in the same time complexity, a 9-spanner with O(n) edges can be constructed.

Keywords

Distributed algorithms graph spanners time complexity Linial’s free model deterministic and randomized algorithms 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Awerbuch, B.: Complexity of network synchronization. Journal of the Association for Computing Machinery 32, 804–823 (1985)zbMATHMathSciNetGoogle Scholar
  2. 2.
    Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems. In: 19th Annual ACM Symposium on Theory of Computing (STOC), May 1987, pp. 230–240. ACM Press, New York (1987)Google Scholar
  3. 3.
    Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Near-linear cost sequential and distributed constructions of sparse neighborhood coverss. In: 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), November 1993, pp. 638–647. IEEE Computer Society Press, Los Alamitos (1993)Google Scholar
  4. 4.
    Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Fast distributed network decompositions and covers. Journal of Parallel and Distributed Computing 39, 105–114 (1996)zbMATHCrossRefGoogle Scholar
  5. 5.
    Awerbuch, B., Berger, B., Cowen, L.J., Peleg, D.: Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing 28(1), 263–277 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Awerbuch, B., Peleg, D.: Sparse partitions. In: 31th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 1990, pp. 503–513. IEEE Computer Society Press, Los Alamitos (1990)Google Scholar
  7. 7.
    Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (α,β)-spanners and purely additive spanners. In: 16th Symposium on Discrete Algorithms (SODA), January 2005, pp. 672–681. ACM-SIAM, New York (2005)Google Scholar
  8. 8.
    Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k − 1)-spanner of O(n 1 + 1/k) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 384–396. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  9. 9.
    Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in \(\tilde{O}(n^2)\) time. In: 15th Symposium on Discrete Algorithms (SODA), January 2004, pp. 271–280. ACM-SIAM, New York (2004)Google Scholar
  10. 10.
    Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing 28(1), 210–236 (1998)zbMATHCrossRefGoogle Scholar
  11. 11.
    Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control 70(1), 32–53 (1986)zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    Cowen, L.J.: Compact routing with minimum stretch. Journal of Algorithms 38(1), 170–183 (2001)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Derbel, B., Mosbah, M., Zemmari, A.: Fast distributed graph partition and application. In: 20th IEEE International Parallel & Distributed Processing Symposium (IPDPS), April 2006, IEEE Computer Society Press, Los Alamitos (2006)Google Scholar
  14. 14.
    Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. Journal of Algorithms 46, 97–114 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Elkin, M.: Computing almost shortest paths. In: 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 53–62. ACM Press, New York (2001)Google Scholar
  16. 16.
    Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. In: 15th Symposium on Discrete Algorithms (SODA), January 2004, pp. 359–368. ACM-SIAM, New York (2004)Google Scholar
  17. 17.
    Elkin, M.: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problems. In: 36th Annual ACM Symposium on Theory of Computing (STOC), May 2004, pp. 331–340. ACM Press, New York (2004)Google Scholar
  18. 18.
    Elkin, M., Peleg, D.: (1 + ε,β)-spanner constructions for general graphs. SIAM Journal on Computing 33(3), 608–631 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  19. 19.
    Elkin, M., Zhang, J.: Efficient algorithms for constructing (1 + ε,β)-spanners in the distributed and streaming models. In: 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), July 2004, pp. 160–168. ACM Press, New York (2004)Google Scholar
  20. 20.
    Gavoille, C., Peleg, D., Pérennès, S., Raz, R.: Distance labeling in graphs. Journal of Algorithms 53(1), 85–112 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Goldberg, A.V., Plotkin, S.A., Shannon, G.E.: Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics 1(4), 434–446 (1988)zbMATHCrossRefMathSciNetGoogle Scholar
  22. 22.
    Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol. 3724, pp. 273–287. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  23. 23.
    Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), July 2004, pp. 300–309. ACM Press, New York (2004)Google Scholar
  24. 24.
    Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: 17th Symposium on Discrete Algorithms (SODA), January 2006, pp. 980–989. ACM-SIAM, New York (2006)CrossRefGoogle Scholar
  25. 25.
    Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. Journal of Algorithms 28(1), 40–66 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  26. 26.
    Linial, N.: Distributive graph algorithms - Global solutions from local data. In: 28th Annual IEEE Symposium on Foundations of Computer Science (FOCS), October 1987, pp. 331–335. IEEE Computer Society Press, Los Alamitos (1987)Google Scholar
  27. 27.
    Linial, N.: Locality in distributed graphs algorithms. SIAM Journal on Computing 21(1), 193–201 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  28. 28.
    Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in O(loglogn) communication rounds. SIAM Journal on Discrete Mathematics 35(1), 120–131 (2005)zbMATHMathSciNetGoogle Scholar
  29. 29.
    Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. In: 20th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 63–71. ACM Press, New York (2001)Google Scholar
  30. 30.
    Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics 13, 383–390 (1975)zbMATHCrossRefMathSciNetGoogle Scholar
  31. 31.
    Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing 15(4), 1036–1053 (1986)zbMATHCrossRefMathSciNetGoogle Scholar
  32. 32.
    Moran, S., Snir, S.: Simple and efficient network decomposition and synchronization. Theoretical Computer Science 243(1-2), 217–241 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  33. 33.
    Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. Journal of Algorithms 20(2), 356–374 (1996)zbMATHCrossRefMathSciNetGoogle Scholar
  34. 34.
    Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)Google Scholar
  35. 35.
    Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM Journal on Computing 30(5), 1427–1442 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  36. 36.
    Peleg, D., Ullman, J.D.: An optimal synchornizer for the hypercube. SIAM Journal on Computing 18(4), 740–747 (1989)zbMATHCrossRefMathSciNetGoogle Scholar
  37. 37.
    Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. Journal of the ACM 36(3), 510–530 (1989)zbMATHCrossRefMathSciNetGoogle Scholar
  38. 38.
    Penso, L.D., Valmir, C.B.: A distributed algorithm to find k-dominating sets. Discrete Applied Mathematics 141(1-3), 243–253 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  39. 39.
    Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. In: 13th Symposium on Discrete Algorithms (SODA), January 2002, pp. 844–851. ACM-SIAM (2002)Google Scholar
  40. 40.
    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. 3580, pp. 261–272. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  41. 41.
    Thorup, M., Zwick, U.: Compact routing schemes. In: 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 2001, pp. 1–10. ACM Press, New York (2001)Google Scholar
  42. 42.
    Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM 52(1), 1–24 (2005)zbMATHCrossRefMathSciNetGoogle Scholar
  43. 43.
    Wenger, R.: Extremal graphs with no C 4’s, C 6’s, or C 10’s. Journal of Combinatorial Theory, Series B 52(1), 113–116 (1991)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Bilel Derbel
    • 1
  • Cyril Gavoille
    • 1
  1. 1.LaBRIUniversité Bordeaux 1TalenceFrance

Personalised recommendations