Removing randomness in parallel computation without a processor penalty
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 162-173
- https://doi.org/10.1109/sfcs.1988.21934
Abstract
Some general techniques are developed for removing randomness from randomized NC algorithms without a blowup in the number of processors. One of the requirements for the application of these techniques is that the analysis of the randomized algorithm uses only pairwise independence. The main new result is a parallel algorithm for the Delta +1 vertex coloring problem with running time O(log/sup 3/ nlog log n) using a linear number of processors on a concurrent-read-concurrent-write parallel random-access machine. The techniques also apply to several other problems, including the maximal-independent-set problem and the maximal-matching problem. The application of the general technique to these last two problems is mostly of academic interest, because NC algorithms using a linear number of processors that have better running times have been previously found.Keywords
This publication has 5 references indexed in Scilit:
- A new parallel algorithm for the maximal independent set problemPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- An improved parallel algorithm for maximal matchingInformation Processing Letters, 1986
- A fast parallel algorithm for the maximal independent set problemPublished by Association for Computing Machinery (ACM) ,1984