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

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, 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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope