Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs
In this paper, we present a linear-time algorithm for substitution decomposition on chordal graphs. Based on this result, we develop a linear-time algorithm for transitive orientation on chordal comparability graphs, which reduces the complexity of chordal comparability recognition from O(n(2)) to O(n+m). We also devise a simple linear-time algorithm for interval graph recognition where no complicated data structure is involved.
interval graph substitution decomposition chordal graph transitive orientation graph recognition triangulated graph analysis of algorithms graph theory modular decomposition cycle-free poset graph partitioning cardinality lexicographic ordering