Extending Partial Suborders

Beitrag in einem Sammelwerk

Details zur Publikation

Autorinnen und Autoren: Fekete SP, Köhler E, Teich J
Herausgeber: Hajo Broersma, Ulrich Faigle, Johann Hurink and Stefan Pickl
Titel Sammelwerk: Electronic Notes in Discrete Mathematics
Verlag: Elsevier BV
Jahr der Veröffentlichung: 2001
Band: Vol. 8
ISSN: 1571-0653


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.

FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Teich, Jürgen Prof. Dr.-Ing.
Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)

Einrichtungen weiterer Autorinnen und Autoren

Technische Universität Berlin
Technische Universität Braunschweig


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.

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.


Zuletzt aktualisiert 2019-23-07 um 07:30