Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

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

20.11.2008

Once again: Connected Components on a CREW-PRAM
Kai Werther
[Download PostScript] [Download PDF]

We present an algorithm to compute the connected components of a graph in parallel time O(log|V| log log|V|) on a CREW-PRAM with a linear number of processors. This closes the gap to the best known (and trivial) lower bound of Ω(log|V|) from previously O(log1/2|V|) to O(log log|V|).

Last Change: 11/20/08 at 12:21:12
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope