A Fast Gray Code Listing of the Perfect Elimination Orderings of a Chordal Graph

Frank Ruskey
University of Victoria

Chordal graphs, sometimes called triangulated graphs, are those that have no induced chordless cycle of length greater than three. Chordal graphs are characterized by the fact that they possess a perfect elimination ordering (PEO), which is class of permutations of its vertices. Given as input a chordal graph, we develop an algorithm for listing all PEO's of the graph in such a way that successive PEO's differ by one or two traspositions of adjacent elements. Furthermore, the algorithm runs in time proportional to the number of PEO's; i.e., in constant amortized time.

These results are provided as an illustration of a general methodology for quickly listing the basic words of any antimatroid, given a fast "oracle" for determining whether two elements can be transposed and still be a basic word.

Return to the Program