An improved distributed algorithm for maximal independent set. (English) Zbl 1411.68175
Krauthgamer, Robert (ed.), Proceedings of the 27th annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, January 10–12, 2016. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 270-277 (2016).
MSC:
| 68W15 | Distributed algorithms |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
