A CLIQUE TREE ALGORITHM FOR PARTITIONING A CHORDAL GRAPH INTO TRANSITIVE SUBGRAPHS

A partitioning problem on chordal graphs that arises in the solution o f sparse triangular systems of equations on parallel computers is cons idered. Roughly the problem is to partition a chordal graph G into the fewest transitively orientable subgraphs over all perfect elimination orderings of G, subject to a certain precedence relationship on its v ertices. In earlier work, a greedy scheme that solved the problem by e liminating a largest subset of vertices at each step was described, an d an algorithm implementing the scheme in time and space linear in the number of edges of the graph was provided. A more efficient greedy sc heme, obtained by representing the chordal graph in terms of its maxim al cliques, is described here. The new greedy scheme eliminates, in a specified order, a largest set of ''persistent leaves,'' a subset of t he leaf cliques in the current graph, at each step. Several new result s about minimal vertex separators in chordal graphs, and in particular , the concept of a critical separator of a leaf clique, are employed t o prove that the new scheme solves the partitioning problem. We provid e an algorithm implementing the scheme in time and space linear in the size of the clique tree. We anticipate that a critical separator of a leaf clique may be a useful concept in other problems on chordal grap hs.