Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

1. Alon N., Babai L., Itai A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567–583 (1986)

   Article  MATH  MathSciNet  Google Scholar 

2. Arikati S.R., Maheshwari A., Zaroliagis C.: Efficient computation of implicit representations of sparse graphs. Discrete Appl. Math. 78(1–3), 1–16 (1997)

   Article  MATH  MathSciNet  Google Scholar 

3. Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: Proceedings of the 30th Symposium on Foundations of Computer Science, pp. 364–369 (1989)

4. Bollobas B.: Extremal Graph Theory. Academic Press, New York (1978)

   MATH  Google Scholar 

5. Cole R., Vishkin U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32–53 (1986)

   Article  MATH  MathSciNet  Google Scholar 

6. Deo, N., Litow, B.: A structural approach to graph compression. In: Proceedings of the MFCS Workshop on Communications, pp. 91–100 (1998)

7. Dujmovic V., Wood D.R.: Graph treewidth and geometric thickness parameters. Discrete Comput. Geom. 37(4), 641–670 (2007)

   Article  MATH  MathSciNet  Google Scholar 

8. Erdős P., Frankl P., Füredi Z.: Families of finite sets in which no set is covered by the union of r others. Isr. J. Math. 51, 79–89 (1985)

   Article  Google Scholar 

9. Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: Proceedings of the 26th ACM Symposium on Principles of Distributed Computing, pp. 53–60 (2007)

10. Goldberg, A., Plotkin, S.: Efficient parallel algorithms for (Δ + 1)- coloring and maximal independent set problem. In: Proceedings of the 19th ACM Symposium on Theory of Computing, pp. 315–324 (1987)

11. Goldberg A., Plotkin S., Shannon G.: Parallel symmetry-breaking in sparse graphs. SIAM J. Discrete Math. 1(4), 434–446 (1988)

    Article  MATH  MathSciNet  Google Scholar 

12. Itai A., Rodeh M.: Symmetry breaking in distributed networks. Inf. Comput. 88(1), 60–87 (1990)

    Article  MATH  MathSciNet  Google Scholar 

13. Kothapalli, K., Scheideler, C., Onus, M., Schindelhauer, C.: Distributed coloring in \({\tilde O(\sqrt{\log n})}\) bit rounds. In: Proceedings of the 20th International Parallel and Distributed Processing Symposium, p. 24 (2006)

14. Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Proceedings of the 19th International Symposium on Distributed Computing, pp. 273–287 (2005)

15. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing, pp. 300–309 (2004)

16. Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: Proceedings of the 24rd ACM Symposium on Principles of Distributed Computing, pp. 60–68 (2005)

17. Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, pp. 7–15 (2006)

18. Linial N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992)

    Article  MATH  MathSciNet  Google Scholar 

19. Luby M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036–1053 (1986)

    Article  MATH  MathSciNet  Google Scholar 

20. Mohar B.: Graph minors and graphs on surfaces. In: Hirschfeld, J.W.P.(eds) Surveys in Combinatorics., pp. 145–163. London Mathematical Society Lecture Note Series 288. Cambridge University Press, Cambridge (2001)

    Google Scholar 

21. Nash-Williams C.: Decompositions of finite graphs into forests. J. Lond. Math. 39, 12 (1964)

    Article  MATH  MathSciNet  Google Scholar 

22. Panconesi A., Srinivasan A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581–592 (1995)

    MathSciNet  Google Scholar 

23. Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications (2000)

24. Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set algorithm for growth bounded graphs. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, pp. 35–44 (2008)

25. Singh G.: Efficient leader election using sense of direction. Distrib. Comput. 10(3), 159–165 (1997)

    Article  Google Scholar 

26. Szegedy, M., Vishwanathan, S.: Locality based graph coloring. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 201–207 (1993)

Download references