A simple parallel algorithm for the maximal independent set problem

Michael Luby

1985 · 343 citations · 12 references

DOIFull text

Open access

Concepts

TL;DR

The paper presents simple parallel algorithms for the maximal independent set problem and develops powerful techniques to convert Monte Carlo algorithms into deterministic ones. The authors propose a Monte Carlo algorithm with a very local property and then use it to derive a simple deterministic algorithm that preserves the same parallel running time. The local property of the algorithm may make it a useful protocol design tool in distributed computing environments and artificial intelligence.

Abstract

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.

References

12