WG 2013 - 39th International Workshop on Graph-Theoretic Concepts in Computer Science, Lübeck/Germany

19. - 21.06.2013

The conference WG 2013 continues the series of 38 previous WG's. Since 1975, it took place twenty one times in Germany, four times in the Netherlands, twice in Austria, the Czech Republic and France as well as once in Italy, Slovakia, Switzerland, Norway, the United Kingdom, Greece and in Israel. WG conferences aim to connect theory and practice by demonstrating how graph-theoretic concepts can be applied to various areas of Computer Science and by extracting new problems from applications. The goal is to present recent results and to identify and explore directions of future research. WG 2013 will be held in the Radisson Blu Senator Hotel in Lübeck.

Vortrag von Bodo Manthey, Assistant Professor, University of Twente, Dep. of Applied Mathematics : Smoothed Analysis des Successive-Shortest-Path-Algorithmus für Minimum-Cost Flows

17.06.2013, 18 Uhr c.t., Seminarraum ITCS 2021, 2. OG, Geb. 64

Bei dem Minimum-Cost-Flow-Problem handelt es sich um ein klassisches kombinatorisches Optimierungsproblem. In den letzten 50 Jahren wurden eine Reihe von Algorithmen für Minimum-Cost-Flows entwickelt, und es scheint, dass sowohl das Problem als auch die Algorithmen gut verstanden sind. Allerdings widersprechen empirische Studien den bewiesenen Worst-Case-Laufzeiten. Der Successive-Shortest-Path-Algorithmus (SSP) beispielsweise hat im Worst-Case exponentielle Laufzeit, zeigt in der Praxis aber eine bessere Laufzeit als einige polynomiale Algorithmen.

Smoothed Analysis ist eine Methode, um Performance-Garantien für Algorithmen zu beweisen, die im Worst-Case schlecht sind. Hierbei wird die erwartete Laufzeit analysiert, wenn Instanzen leicht "verrauscht" werden. Dieses Verrauschen kann zum Beispiel Messfehler modellieren.

Um diese Diskrepanz zwischen Worst-Case- und beobachteter Laufzeit von SSP zu erklären, führen wir eine Smoothed Analysis von SSP durch. Wir beweisen eine Smoothed-Laufzeit von O(nm*phi*(m+n*log n)), wobei phi der Smoothing-Parameter ist. Dies zeigt, dass Worst-Case-Instanzen für SSP nicht robust sind und dass es unwahrscheinlich ist, in der Praxis eine Worst-Case-Instanz zu bekommen.

Der Vortrag basiert auf einer Zusammenarbeit mit Tobias Brunsch, Heiko Röglin (Universität Bonn) und Kamiel Cornelissen (Universiteit Twente).

Vortrag von Dr. Christian Rosanke, Institut für Informatik, Uni Rostock : Zur Charakterisierung von Blattpotenzen

30.04.2013

Ursprünglich durch eine biologische Fragestellung motiviert, werden Blattpotenzen heute als neue natürliche Teilklasse der gut untersuchten chordalen Graphen verstanden. Während ein Graph genau dann chordal ist, wenn er für einen Baum T der Durschnittsgraph einer Menge von Teilbäumen in T ist, verlangen Blattpotenzen zusätzlich, dass jeder Teilbaum eine Scheibe bildet, d.h. für einen Zentralknoten v in T und einen Radius r genau die Knoten von T enthält, die zu v höchstens Abstand r haben. Damit ergeben die Blattpotenzen außerdem eine schöne Verallgemeinerung der bekannten Unit-Interval-Graphen, bei denen T ein Pfad sein muss und alle Radi gleich.

Während chordale Graphen und Unit-Interval-Graphen in Linearzeit erkannt werden können und seit langem durch verbotene induzierte Teilgraphen charakterisiert wurden, sind effiziente Erkennungsalgorithmen oder eine vollständige Charakterisierung der Blattpotenten bisher nicht bekannt. Der Vortrag stellt einen neuen Zugang zu diesen Fragestellungen vor und präsentiert erste neue Ergebnisse, die auf eine baldige Lösung hoffen lassen.