A simple parallel algorithm for the maximal independent set problem
Michael G. Luby · 1985
Simple parallel algorithms for the maximal independent set (MIS) problem are presented. The first algorithm is a Monte Carlo algorithm with a very local property. The local property of this algorithm may make it a useful protocol design tool in distributed computing environments and artificial intelligence. One of the main contributions of this paper is the development of powerful and general techniques for converting Monte Carlo algorithms into deterministic algorithms. These techniques are used to convert the Monte Carlo algorithm for the MIS problem into a simple deterministic algorithm with the same parallel running time.
Cited by 349 works. doi:10.1145/22145.22146 Open-access PDF
Authors
References
- An introduction to probability theory and its applications
- Neural networks and physical systems with emergent collective computational abilities.
- How to share a secret
- A complexity theoretic approach to randomness
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- The complexity of approximate counting
- A taxonomy of problems with fast parallel algorithms
- A fast parallel algorithm for the maximal independent set problem
- Size bounds and parallel algorithms for networks