Abstract: Partielle Ordnungen auf einer Menge V können verallgemeinert werden, indem man zusätzlich zu den üblichen Präzedenzbedingungen "`v \in V liegt über allen Elementen aus W\subset V"' (AND-Bedingung) disjunktive Bedingungen der Form "`v liegt über mindestens einem Element aus W"' (OR-Bedingung) erlaubt. In Analogie zu der Darstellung gewöhnlicher partieller Ordnungen durch gerichtete azyklische Graphen (bzw. Hasse-Diagramme) können diese verallgemeinerten Präzedenzbedingungen durch sogenannte AND/OR-Netzwerke repräsentiert werden, die jedoch nicht mehr notwendigerweise azyklisch sind. Neben Problemen im Scheduling finden solche Netzwerke u.a. bei Spielen auf Graphen, bei Läsung von Satisfizierbarkeitsproblemen (Horn Klauseln) und in der KI (automatisches Beweisen) Anwendung. Der Vortrag geht auf einige dieser Anwendungen ein und beschreibt Basisalgorithmen auf AND/OR-Netzwerken. Hierzu gehören der Test auf Erfüllbarkeit der AND/OR Bedingungen, die Berechnung der transitiven Hülle und transitiven Reduktion, sowie - im Rahmen des Scheduling - die Berechnung frühester Startzeiten. Während viele dieser Probleme effizient gelöst werden können, ist kein polynomialer Algorithmus für den allgemeinen Fall frühester Startzeiten bekannt, obwohl das zugehörige Entscheidungsproblem in P \cap coNP liegt. Die vorgestellten Ergebnisse beruhen auf gemeinsamer Arbeit mit Martin Skutella und Frederik Stork.
Kolloquium - 16 Uhr s.t.
Abstract: In dem Vortrag geht es um ein Lemma, mit dem sich untere Schranken für die Zusammenhangszahl gewisser Graphen beweisen lassen. Folgende Anwendungen möchte ich vorführen: