Inproceedings,
Linear-time transitive orientation
In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, (1997)
Abstract
The transitive orientation problem is the problem of assigning a direction to each edge of a graph so that the resulting digraph is transitive. A graph is a comparability graph if such an assignment is possible. We describe an O(n + m) algorithm for the transitive orientation problem, where n and m are the number of vertices and edges of the graph; full details are given in IS. This gives linear time bounds for maximum clique and minimum vertex coloring on comparability graphs, recognition of two-dimensional partial orders, permutation graphs, cointerval graphs, and triangulated comparability graphs, and other combinatorial problems on comparability graphs and their complements.
