Fast Parallel Decomposition by Clique Separators
Elias Dahlhaus, Marek Karpiński · 1988
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 CREW-PRAM. It is the first sublinear parallel time (and therefore sequential sublinear space) algorithm for this problem.