Fast parallel algorithms for the clique separator decomposition
Elias Dahlhaus, Marek Karpiński, Mark B. Novick · Symposium on Discrete Algorithms · 1990
We give an efficient {\it NC} algorithm for finding a clique separator decomposition of an {\it arbitrary} graph, that is, a series of cliques whose removal disconnects the graph. This algorithm allows one to extend a large body of results which were originally formulated for chordal graphs to other classes of graphs. Our algorithm is optimal to within a polylogarithmic factor of Tarjan''s $O(mn)$ time sequential algorithm. The decomposition can also be used to find {\it NC} algorithms for some optimization problems on special families of graphs, assuming these problems can be solved in {\it NC} for the prime graphs of the decomposition. These optimization problems include: finding a maximum-weight clique, a minimum coloring, a maximum-weight independent set, and a minimum fill-in elimination order. We also give the first parallel algorithms for solving these problems by using the clique separator decomposition. Our maximum-weight independent set algorithm applied to chordal graphs yields the most efficient known parallel algorithm for finding a maximum-weight independent set of a chordal graph.