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

Fast Parallel Algorithms for the Clique Separator Decomposition
Elias Dahlhaus, Marek Karpinski, Mark Novick
[Download PostScript] [Download PDF]

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.

Last Change: 12/10/08 at 16:17:27
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope