TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1989

COGA 5-Wheel


zur Navigation

Preprints 1989

Computationally Tractable Classes of Ordered Sets
Zitatschlüssel Report-181-1987
Autor Rolf H. Möhring
Buchtitel Algorithms and Order, 1989
Seiten 105-193
Jahr 1987
Nummer 181
Herausgeber I. Rival
Verlag Kluwer Acad. Publ., Dordrecht
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung Ordered sets have recently gained much importance in many applied and theoretical problems in computer science and operations research ranging from project planning via processor scheduling to sorting and retrieval problems. These problems involve partial orders as their basic structure, e.g. as precedence constraints in scheduling problems, or as comparability relation among the objects to be sorted or retrieved. Since many of the involved problems are NP-hard in general, much attention has recently been given to special classes of partial orders with ``nice'' strutural properties that lend themselves the design of efficient methods, and for obtaining bounds by structural relaxation in more general situations. Typical such classes are: series parallel partial orders, N-free partial orders, interval orders, two-dimensional partial orders, and partial orders with special decomposition properties. This area of ``computationally tractable'' classes of partial orders shows many similarities and interactions with algorithmic complexity of their recognition. In addtion, we present the tractibility of these different classes on several applications dealing with scheduling and sorting.
Typ der Publikation Preprint
Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe