Linear-time transitive orientation

. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, (1997)


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.

Links and resources

BibTeX key:
search on:

Comments and Reviews  

There is no review or comment yet. You can write one!


Cite this publication