MIS in the Congested Clique Model in $O(\log \log \Delta)$ Rounds

Luby, M.: A simple parallel algorithm for the maximal independent set problem. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing. pp. 1–10. STOC ’85, ACM, New York, NY, USA (1985), http://doi.acm.org/10.1145/22145.22146

1985

Earlier work this paper cites.

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 (Dec 1986), http://dx.doi.org/10.1016/0196-6774(86)90019-2

1986

Earlier work this paper cites.

Linial, N.: Distributive graph algorithms-global solutions from local data. In: 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987. pp. 331–335 (1987), https://doi.org/10.1109/SFCS.1987.20

1987

Earlier work this paper cites.

Peleg, D.: Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)

Original

2000

Earlier work this paper cites.

Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: Mst construction in o(log log n) communication rounds. In: Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures. pp. 94–100. SPAA ’03, ACM, New York, NY, USA (2003), http://doi.acm.org/10.1145/777412.777428

2003

Earlier work this paper cites.

Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing. pp. 300–309. PODC ’04, ACM, New York, NY, USA (2004), http://doi.acm.org/10.1145/1011767.1011811

2004

Earlier work this paper cites.

Lotker, Z., Patt-Shamir, B., Pavlov, E., Peleg, D.: Minimum-weight spanning tree construction in o(log log n) communication rounds. SIAM J. Comput. 35(1), 120–131 (Jul 2005), https://doi.org/10.1137/S0097539704441848

2005

Earlier work this paper cites.

Fanghänel, A., Kesselheim, T., Vöcking, B.: Improved algorithms for latency minimization in wireless networks. Theor. Comput. Sci. 412(24), 2657–2667 (May 2011), http://dx.doi.org/10.1016/j.tcs.2010.05.004

2010

Earlier work this paper cites.

Lenzen, C.: Optimal deterministic routing and sorting on the congested clique. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing. pp. 42–50. PODC ’13, ACM, New York, NY, USA (2013), http://doi.acm.org/10.1145/2484239.2501983

2013

Cited alongside, same era.

Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing. pp. 367–376. PODC ’14, ACM, New York, NY, USA (2014), http://doi.acm.org/10.1145/2611462.2611493

2014

Cited alongside, same era.

Hegeman, J.W., Pemmaraju, S.V.: Lessons from the congested clique applied to mapreduce. In: Halldórsson, M.M. (ed.) Structural Information and Communication Complexity. pp. 149–164. Springer International Publishing, Cham (2014)

2014

Cited alongside, same era.

Hegeman, J.W., Pemmaraju, S.V., Sardeshmukh, V.B.: Near-constant-time distributed algorithms on a congested clique. In: Kuhn, F. (ed.) Distributed Computing. pp. 514–530. Springer Berlin Heidelberg, Berlin, Heidelberg (2014)

Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 270–277. SODA ’16, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2016), http://dl.acm.org/citation.cfm?id=2884435.2884455

2016

Later among the works it cites.

Ghaffari, M., Parter, M.: Mst in log-star rounds of congested clique. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. pp. 19–28. PODC ’16, ACM, New York, NY, USA (2016), http://doi.acm.org/10.1145/2933057.2933103

2016

Later among the works it cites.

Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: Lower and upper bounds. J. ACM 63(2), 17:1–17:44 (Mar 2016), http://doi.acm.org/10.1145/2742012

2016

Later among the works it cites.

Le Gall, F.: Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In: Gavoille, C., Ilcinkas, D. (eds.) Distributed Computing. pp. 57–70. Springer Berlin Heidelberg, Berlin, Heidelberg (2016)