@duerrschnabel

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.

Links and resources

URL:
BibTeX key:
Mcconnell97linear-timetransitive
search on:

Comments and Reviews  
(0)

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

Tags


Cite this publication