JavaScript is disabled for your browser. Some features of this site may not work without it.
NC Algorithms for the Clique Separator Decomposition

Author
Novick, Mark B.
Abstract
We give the first NC algorithm for finding a clique separator decomposition of a 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 a parallel version of Tarjan's sequential algorithm for solving this problem. 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 ordering. We also give the first parallel algorithms for solving these problems by using the clique separator decomposition. Our maximum-weight independent set alforithm applied to chordal graphs yields the most efficient known parallel algorithm for finding a maximum-weight independent set of a chordal graph.
Date Issued
1989-03Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-974
Type
technical report