
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
8534

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 maximumweight clique, a minimum coloring, a maximumweight independent set, and a minimum fillin elimination order. We also give the first parallel algorithms for solving these problems by using the clique separator decomposition. Our maximumweight independent set algorithm applied to chordal graphs yields the most efficient known parallel algorithm for finding a maximumweight independent set of a chordal graph. 

Last Change:
12/10/08 at 16:17:27
Deutsch 
University of Bonn > Department of Computer Science > Chair V 