Inhalt des Dokuments
Preprint 697-2000
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Extending partial suborders and implication classes
- Authors
- Sándor P. Fekete, Ekkehard Köhler, and Jürgen Teich
- Classification
-
MSC: primary: 05C20 Directed graphs , tournaments secondary: 06A07 Combinatorics of partially ordered sets - Keywords
-
scheduling, precedence constraints, transitive orientation, interval graphs, partial orders.
- Abstract
-
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.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe