1985 · 343 citations · 12 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisMonte Carlo MethodsMonte Carlo SimulationParallel Algorithm DesignRandomized AlgorithmsRandomized ComputationIndependent Set AlgorithmsMonte Carlo AnalysisRandomized Parallel AlgorithmsSimple Algorithm
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.
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.
12
Adi Shamir · Communications of the ACM · 1979 · 13.5K citations · Full text
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael Luby · SIAM Journal on Computing · 1986 · 1.1K citations