|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-Reports 1985-1989 | Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V | |
|
8525
|
Fast Parallel Decomposition by Clique Separators
Elias Dahlhaus, Marek Karpinski [Download PostScript] [Download PDF] We design a fast parallel algorithm for decomposing an arbitrtary graph by the clique separators. The algorithm works in $O(log^2 n)$ parallel time and $O(n^4)$ processors on a CREW-PRAM. It is the first sublinear parallel time (and therefore sequential sublinear space) algorithm for this problem. |
|
|
Last Change:
12/05/08 at 09:11:40
|
University of Bonn -> Department of Computer Science -> Chair V | |