10.12.2008

We design a first efficient parallel algorithm for decomposing an arbitrary graph by clique separators. The algorithm works in 0(log³n) parallel time and O(n³) 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³) time algorithm of Tarjan [Ta 85].