Department of Computer Science
 
Chair V

 
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
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(log3n) parallel time and O(n3) 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(n3) 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