|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-Reports 1994 | Copyright 1994 University of Bonn, Department of Computer Science, 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
|
University of Bonn -> Department of Computer Science -> Chair V | |