A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael G. Luby · SIAM Journal on Computing · 1986
Two basic design strategies are used to develop a very simple and fast parallel algorithms for the maximal independent set (MIS) problem. The first strategy consists of assigning identical copies of a simple algorithm to small local portions of the problem input. The algorithm is designed so that when the copies are executed in parallel the correct problem output is produced very quickly. A very simple Monte Carlo algorithm for the MIS problem is presented which is based upon this strategy. The second strategy is a general and powerful technique for removing randomization from algorithms. This strategy is used to convert the Monte Carlo algorithm for this MIS problem into a simple deterministic algorithm with the same parallel running time.
Cited by 1,147 works. doi:10.1137/0215074
Authors
References
- Neural networks and physical systems with emergent collective computational abilities.
- How to share a secret
- An Introduction to Probability Theory and Its Applications, Vol. 2
- Universal classes of hash functions
- Parallel models of associative memory
- On colouring the nodes of a network
- Parallelism in random access machines
- A taxonomy of problems with fast parallel algorithms
- On the application of the Borel-Cantelli lemma
- On a Set of Almost Deterministic $k$-Independent Random Variables