Fast Parallel Algorithms for the Clique Separator Decomposition

TitleFast Parallel Algorithms for the Clique Separator Decomposition
Publication TypeTechnical Report
Year of Publication1989
AuthorsDahlhaus, E., Karpinski M., & Novick M. B.
Other Numbers538

We give an efficient NC algorithm for finding a clique separator decomposition of an arbitary 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 polyalgorithmic factor of Tarjan's O(nm) time sequential algorithm. The decomposition can also be used to find NC algorithms for some optimization problems on special families of graphs, assuming these problems can be solved in 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 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.

Bibliographic Notes

ICSI Technical Report TR-89-039

Abbreviated Authors

E. Dahlhaus, M. Karpinski, and M. B. Novick

ICSI Publication Type

Technical Report