Transitive orientation in 0(n 2 ) time
Jeremy Spinrad · 1983
This paper presents an algorithm for the transitive graph orientation problem which runs in 0(n2) time. The best previous algorithms for this problem required 0(n3) time. Transitive orientation is the slowest part of several graph recognition problems, so the new algorithm immediately improves the complexity of algorithms for recognizing comparability graphs, permutation graphs, and circular permutation graphs.