Mixed graphs and partial orders.

• Applicant: Professor Dr. Rolf H. Möhring
• Subject Area: Mathematics
• Term: from 2001 to 2004
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5467699

Die Objekte, die im Mittelpunkt dieses Vorhabens stehen, sind motiviert durch eine Problemstellung aus dem Scheduling. Gegeben ist eine partielle Ordnung P und eine Menge F von Antiketten von P. Dabei modelliert P die aus technischen Gründen notwendigen Reihenfolgebeziehungen. In F sind dagegen diejenigen Mengen von Arbeitsgängen enthalten, die zwar gleichzeitig durchgeführt werden könnten, ohne die gegebene Reihenfolge P zu verletzen, die sich aber aus Mangel an Ressourcen nicht gleichzeitig abarbeiten lassen. Jede Erweiterung von P, in der keine der Mengen aus F eine Antikette ist, stellt also eine zulässige Lösung dar. Besonders interessant sind hier die minimal zulässigen Erweiterungen von P, also zulässige Erweiterungen, deren echte Teilordnungen allesamt unzulässig sind. Die Bedeutung minimal zulässiger Erweiterungen geht jedoch weit über die Anwendung im Scheduling hinaus. Bereits für Mengensysteme F, die nur aus zweielementigen Mengen bestehen, ergeben sich zahlreiche Beziehungen zu wichtigen Fragestellungen in der Ordnungstheorie, der Graphentheorie und anderen Teilen der Kombinatorik. Die minimal zulässigen Erweiterungen von P nennen wir pseudolineare Erweiterungen, wenn das zugrunde liegende System F nur zweielementige Antiketten enthält. ... In diesem Teilprojekt möchten wir uns zunächst auf die Untersuchung pseudolinearer Erweiterungen beschränken. Aufbauend auf einem guten Verständnis dieser Objekte ist allerdings die Untersuchung allgemeiner Klassen von minimal zulässigen Ordnungen eine attraktive langfristige Perspektive.

• DFG Programme: Research Units
• Subproject of: FOR 413: Algorithms, Structure, Randomness