On Generating Strong Elimination Orderings of Strongly Chordal Graphs

We present a conceptually simple algorithm to generate an ordering of the vertices of an undirected graph. The ordering generated turns out to be a strong elimination ordering if and only if the given graph is a strongly chordal graph. This algorithm makes use of maximum cardinality search and lexicographic breadth first search algorithms which are used to generate perfect elimination orderings of a chordal graph. Our algorithm takes O(k2n) time where k is the size of the largest minimal vertex separator and n denotes the number vertices in the graph. The algorithm provides a new insight into the structure of strongly chordal graphs and also gives rise to a new algorithm of the same time complexity for recognition of strongly chordal graphs.