We consider the following problem called transitive ordering
with precedence constraints (TOP):
Given a partial order P=(V,&;) and an (undirected)
graph G=(V,E) such that all relations in P
are represented by edges in G. Is there a transitive
orientation D=(V,A) of G, such that P is contained in
D?
This problem arises naturally in the context of scheduling,
where P describes a set of precedence constraints,
and the graph G is the (temporal) comparability graph
of jobs. Korte and Möhring (1985) have given
a linear-time algorithm for deciding TOP. However,
their approach is only useful when the full set of edges in
G is known. When running a branch-and-bound
algorithm for solving a scheduling problem, these edges
are only known partially, but they may already prohibit
the existence of a feasible solution.
We give a pair of necessary and sufficient conditions
on graphs G in terms of forbidden substructures.
Thus, our conditions can be used
quite effectively in the context of a branch-and-bound framework.
