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


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
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope