Fekete SP, Köhler E, Teich J (2001)
Publication Type: Book chapter / Article in edited volumes
Publication year: 2001
Publisher: Elsevier BV
Edited Volumes: Electronic Notes in Discrete Mathematics
Book Volume: Vol. 8
We consider the problem of finding a transitive orientation T of a comparability graph G = (V, E), such that a given partial order P is extended. Existing algorithms for this problem require the full knowledge of E, so they are of limited use in the context of a branch-and-bound algorithm, where only parts of E may be known at any stage. We present a new approach to the problem by describing a pair of necessary and sufficient conditions for the existence of an orientation T, based on two simple forbidden subconfigurations. This allows it to solve higher-dimensional packing and scheduling problems of interesting size to optimality. We have implemented this approach and the computational results are convincing.
APA:
Fekete, S.P., Köhler, E., & Teich, J. (2001). Extending Partial Suborders. In Hajo Broersma, Ulrich Faigle, Johann Hurink and Stefan Pickl (Eds.), Electronic Notes in Discrete Mathematics. Elsevier BV.
MLA:
Fekete, Sandor P., Ekkehard Köhler, and Jürgen Teich. "Extending Partial Suborders." Electronic Notes in Discrete Mathematics. Ed. Hajo Broersma, Ulrich Faigle, Johann Hurink and Stefan Pickl, Elsevier BV, 2001.
BibTeX: Download