Publication Details
Title: Removing Randomness in Parallel Computation Without a Processor Penalty
Author: M. Luby
Group: ICSI Technical Reports
Date: July 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-44.pdf
Overview:
We develop some general techniques for converting randomized parallel algorithms into deterministic parallel 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. Our main new result is a parallel algorithm for coloring the vertices of an undirected graph using at most delta + 1 distinct colors in such a way that no two adjacent vertices receive the same color, where delta is the maximum degree of any vertex in the graph. The running time of the algorithm is O((log (superscript 3)) n log log n) using a linear number of processors on a concurrent read, exclusive write (CREW) parallel random access machine (PRAM). Our 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 parallel algorithms that use a linear number of processors which have better running times have been previously found [Israeli, Siloach86], [Goldberbg, Spencer 87].
Bibliographic Information:
ICSI Technical Report TR-89-044
Bibliographic Reference:
M. Luby. Removing Randomness in Parallel Computation Without a Processor Penalty. ICSI Technical Report TR-89-044, July 1989
Author: M. Luby
Group: ICSI Technical Reports
Date: July 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-44.pdf
Overview:
We develop some general techniques for converting randomized parallel algorithms into deterministic parallel 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. Our main new result is a parallel algorithm for coloring the vertices of an undirected graph using at most delta + 1 distinct colors in such a way that no two adjacent vertices receive the same color, where delta is the maximum degree of any vertex in the graph. The running time of the algorithm is O((log (superscript 3)) n log log n) using a linear number of processors on a concurrent read, exclusive write (CREW) parallel random access machine (PRAM). Our 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 parallel algorithms that use a linear number of processors which have better running times have been previously found [Israeli, Siloach86], [Goldberbg, Spencer 87].
Bibliographic Information:
ICSI Technical Report TR-89-044
Bibliographic Reference:
M. Luby. Removing Randomness in Parallel Computation Without a Processor Penalty. ICSI Technical Report TR-89-044, July 1989