Desktop-Bild
WICHTIG

Seminar: Shortest Paths: going beyond Dijkstra

We investigate several extensions of the classical shortest path problem as integrating uncertainties into the problem setting or dealing with multiple objective functions. In all cases, we discuss the complexity and efficient algorithms to solve the new problem.

Lecturer
Prof. Dr. Christina Büsing
General remarks
  • The seminar is heavily oriented towards theory and mathematics (definitions, theorems, proofs).
  • The seminar requires good knowledge of the theory courses in the informatics bachelor.
  • Every lecture is centered around a recent research paper (see the list below).
Time line
  • Briefing: t.b.a.
  • 5-Min Talks: t.b.a.
  • Presentations: t.b.a.
Required contributions
  • A lecture of 40-45 minutes: First a soft introduction into the considered problems; then a short survey on the derived results; then a technical part that explains the most beautiful and most interesting parts of the paper.
  • Target audience are the other students participating in the seminar.
  • In general, only some (small) part of the paper can be presented in 40-45 minutes. The selection of results for your lecture is one of the required contributions.
  • At the day of the lecture, you have to prepare a report that summarizes your lecture within 10-12 pages, in English or in German.
  • Attendance of all lectures is compulsory for all participants.
Topics
  • On the Robust Shortest Path Problem (Gang Yu, Jian Yang, 1998)
  • New models for the robust shortest path problem: complexity, resolution and generalization (Virgine Gabrel, Cecile Murat, Lei Wu, 2013)
  • Online shortest paths: Online shortest paths with confidence intervals for routing in a time varying random network (Stephane Chretien, Christophe Guyeux, 2018)
  • Online shortest paths: An online shortest path algorithm for reliable routing in schedule-based transit networks considering transfer failure probability (Alireza Khani, 2019)
  • The Shortest Path Game: Complexity and Algorithms (Andreas Darmann, Ulrich Pferschy, Joachim Schaer, 2014)
  • Selected Multicriteria shortest path problems (Tarapata, 2017)
  • Label Correcting Methods to Solve Multicriteria Shortest Path Problems (F Guerriero, Musmanno, 2001)
  • Space-efficient, Fast and Exact Routing in Time-Dependent Road Networks (Dorothea Wagner, Ben Strasser, Tim Zeitz, 2021)
  • Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles (Dorothea Wagner, Moritz Baum, Julian Dibbelt, Tobias Zündorf, 2020)
  • Finding the k Shorest Paths (David Ebstein, 1998)
last modified: 14/06/2021 - 13:12