Fast Parallel Algorithms for the Clique Separator Decomposition
Title | Fast Parallel Algorithms for the Clique Separator Decomposition |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Dahlhaus, E., Karpinski M., & Novick M. B. |
Other Numbers | 538 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-89-39.pdf |
Bibliographic Notes | ICSI Technical Report TR-89-039 |
Abbreviated Authors | E. Dahlhaus, M. Karpinski, and M. B. Novick |
ICSI Publication Type | Technical Report |