Article ID Journal Published Year Pages File Type
428335 Information Processing Letters 2007 7 Pages PDF
Abstract

We consider the problem of finding a transitive orientation of a comparability graph, such that the edge set of its covering graph contains a given subset of edges. We propose a solution which employs the classical technique of modular tree decomposition. The method leads to a polynomial time algorithm to construct such an orientation or report that it does not exist.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics