Extending Partial Suborders

Fekete SP, Köhler E, Teich J (2001)

Publication Type: Book chapter / Article in edited volumes

Publication year: 2001

Journal

Electronic Notes in Discrete Mathematics Elsevier BV

Publisher: Elsevier BV

Edited Volumes: Electronic Notes in Discrete Mathematics

Book Volume: Vol. 8

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.

Authors with CRIS profile

Jürgen Teich Lehrstuhl für Informatik 12 (Hardware-Software-Co-Design)

Involved external institutions

Technische Universität Braunschweig DE Germany (DE) Technische Universität Berlin DE Germany (DE)

How to cite

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