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.