direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 697-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Extending partial suborders and implication classes
primary: 05C20 Directed graphs , tournaments
secondary: 06A07 Combinatorics of partially ordered sets
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe