A Fast Gray Code Listing of the Perfect Elimination Orderings of a Chordal Graph
Frank Ruskey, University of Victoria

Abstract : 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.

Announcement Poster in PDF