Kürzeste-Wege-Algorithmen

Theoretische Untersuchung von Kürzeste-Wege-Algorithmen

Bachelor- oder Masterarbeit

In den letzten Jahren wurden große Fortschritte bei der Entwicklung von Techniken erzielt, die es erlauben Kürzeste-Wege-Anfragen für große Graphen sehr viel schneller zu beantworten als Dijkstra’s Algorithmus dies kann. Leider sind all diese Beschleunigungstechniken heuristisch in ihrer Laufzeit und wurden bis jetzt fast ausschließlich auf Straßengraphen getestet.

Dadurch eröffnet sich mit der theoretischen Untersuchung dieser Techniken ein neuer, bis jetzt nicht untersuchter Forschungsbereich mit starker praktischer Bedeutung. Am Lehrstuhl sind viele Real-Welt-Daten vorhanden, so dass bei Interesse die theoretische Arbeit auch durch eine praktische Untersuchung ergänzt oder teilweise ersetzt werden kann.

Art

Bachelor- oder Masterarbeit

Ziele

Ziel der Arbeit ist die Modellierung aktueller Beschleunigungstechniken in einem einheitlichen Framework sowie die Erarbeitung von Ausagen zum Laufzeitverhalten der einzelnen Techniken.

Vorraussetzung

fundierte algorithmische Kenntnisse

Kontakt