Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1996 Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V
85159

A note on improving the running time of a class of parallel algorithms using randomization
Carsten Dorgerloh, Juergen Wirtgen
[Download PostScript] [Download PDF]

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.

Last Change: 08/18/99 at 13:00:38
 English
Universität Bonn -> Institut für Informatik -> Abteilung V