« Forschungslandschaft: Projekte

Viele Optimierungsprobleme auf Graphen aus der realen Welt unterliegen häufigen, kleinen Änderungen. Mit dynamischen Graphenalgorithmen möchte man optimale Lösungen nach Änderungen schneller aktualisieren, als es durch Neuberechnen möglich wäre. Im Mittelpunkt dieses Projekts stehen als konkrete Anwendungen von dynamischen Graphenalgorithmen

• stochastische Vorhersagen in dynamischen Transportnetzwerken für die Robustheitsanalyse und die Fahrplanauskunft;
• eine passagierfreundliche Anschlussdisposition im Bahnverkehr;
• die Netzwerkanalyse zeitabhängiger Netze mit Anwendungen in Flugnetzwerken.
Unter Verwendung des breiten Spektrums der Techniken des Algorithm Engineering sollen die bestehenden Lücken zu praktisch anwendbaren Lösungen geschlossen werden.  Ausgehend von realistischen Anwendungsmodellen, die die Anforderungen aus der Praxis adäquat abbilden, müssen im Entwurf geeignete speicherplatzeffiziente Datenstrukturen entwickelt werden, während in der Analyse realistische Sequenzen dynamischer Änderungen untersucht werden. Basierend auf sorgfältigen und flexiblen Implementationen soll in systematischen Experimenten untersucht werden, welche Eigenschaften der Netzwerke bzw. Updatesequenzen effiziente Lösungen ermöglichen.