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


Abstract


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


Zitierweisen

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: 

Zuletzt aktualisiert 2019-23-07 um 07:30