Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428335 | Information Processing Letters | 2007 | 7 Pages |
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