Extending partial suborders and implication classes

Sándor P. Fekete, Ekkehard Köhler, and Jürgen Teich

scheduling, precedence constraints, transitive orientation, interval graphs, partial orders.

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.

Download as [PDF] [ps.gz]