
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 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 CREWPRAM. 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
Deutsch 
University of Bonn > Department of Computer Science > Chair V 