Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
Wen−Lian Hsu, Tze-Heng Ma · SIAM Journal on Computing · 1998
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.