Construction of a simple elimination scheme for a chordal comparability graph in linear time
Chordal graphs and comparability graphs are two classic graph classes playing a crucial role in algorithmic graph theory of perfect graphs. It is easy to see that chordal comparability graphs are strongly chordal---an important subclass of chordal graphs---and thus have a simple elimination ordering. This paper shows how to find such an ordering of a given chordal comparability graph by using cardinality lexicographic breadth-first search. This implies a linear time algorithm for the maximum matching problem on those graphs.
scientific article; zbMATH DE number 1271080