
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
8531 10.12.2008 
Efficient Parallel Algorithm for Clique Separator Decomposition
Elias Dahlhaus and Marek Karpinski [Download PostScript] [Download PDF] We design a first efficient parallel algorithm for decomposing an arbitrary graph by clique separators. The algorithm works in 0(log^{3}n) parallel time and O(n^{3}) processors on a CREW PRAM. The theory of clique separators is directly related to the theory of elimination orderings of arbitrary graphs, and is used in efficient algorithms for Gaussian elimination of sparse symmetric matrices [Ro 70], [Ro 73], [RTL 76], [Ta 85]. It is the first sublinear parallel time (and therefore sequential parallel space) algorithm for the clique decomposition, and at the same time an optimal algorithm up to the polylogarithmic factor with respect to the best sequential O(n^{3}) time algorithm of Tarjan [Ta 85]. 

Last Change:
12/10/08 at 15:15:59
Deutsch 
University of Bonn > Department of Computer Science > Chair V 