A note on improving the running time of a class of parallel
algorithms using randomization
Abstract:
A natural method to avoid memory access conflicts in EREW-PRAM
graph algorithms is to compute a large independent set in a
constant-degree-bounded conflict graph. Many EREW-PRAM algorithms use results
from \cite{CoVi86}, \cite{GoPlSh87}, which can be used to compute such a set
in $\O$$(\log^* n)$ parallel time. This paper gives an $\O$$(1)$ time
randomized algorithm using $\O$$(n)$ processors for that problem. Our
algorithm improves with high probability the running time of many
EREW-PRAM algorithms.
85159-CS.ps.gz (35855 bytes, 7 pages)
Note:
This WWW-Server is still under construction! Please report any problems with our server by Email to:
webmaster@theory.cs.uni-bonn.de
[
University of Bonn
|
Department of Computer Science
|
Chair V
]
Last updated: Mon May 12 15:41 1997