direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2000

Extending partial suborders and implication classes
Zitatschlüssel Report-697-2000
Autor Sándor P. Fekete and Ekkehard Köhler and Jürgen Teich
Jahr 2000
Nummer 697
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We consider the following problem called transitive ordering with precedence constraints (TOP): Given a partial order $P=(V,\prec)$ 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag