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