Ferienakademie im Sarntal: Distance Problems in Networks  Theory and Practice
Introduction
At first sight, it might seem that with Dijkstra's algorithm all has been said about the computation of shortest paths in networks with nonnegative edge weights. Looking more closely, however, one discovers a lot of unsolved theoretical and practical problems in this field. Especially with the global use of GPS based mobile devices this classical field once again becomes quite important.
In course 2, we will first cover the wellknown algorithms in this field, focusing on more recent research. Besides (rather theoretical) results about spanners, distance oracles, and distance labellings, we will treat the newest developments regarding the sped up computation of shortest paths in transportation networks as they are used in modern routing planners and navigation devices.
Lecturers
The course will be held by Prof. Mayr from Technische Universität München and Prof. Funke from Universität Stuttgart. The guest lecturer, Prof. Wanka from FriedrichAlexanderUniversität ErlangenNürnberg, will speak about
Finding Satisfying Assignments by Random Walk. The course is organized and accompanied by Stephan Ritscher from Technische Universität München.
Presentations
Each student will have 90 minutes for the presentation which can be organised quite freely. There are, among others, the following possibilities:
 interactive development of an algorithm using the whiteboard,
 presentation of a computer program which demonstates the method,
 slide presentation using the projector (a LaTeX template is available here).
About half of the time slot should be reserved for discussions, questions and interaction with the audience. One could, e.g., give a 45 minute slide presentation, leaving 45 minutes for questions and discussions.
Thus, in each session we will have about 2 presentations. The language for presentations is English.
You will also have to write a paper of 67 pages which gives an introduction into the subject of your talk on the level of the course. Please use the LaTeX template since all presentations will be compiled into one single document in the end.
After the course, all presentations and papers will be collected and made available on the course homepage. The participants will also receive a CDROM contatining the talks and pictures from the course. Therefore all students will have to overhaul their presentations and finish the papers until (at latest) two weeks after the seminar (15. October 2010).
Topics
An overview of speedup techniques for shortest path computations is given by
Dorothea Wagner and Thomas Willhalm. It is recommended to all students to have a look at this article before preparing the own presentation.
Topic 
Student 
Literature 
1. Classical ShortestPath Algorithms 
Nesrine Damak
Slides, Paper 
 Dijkstra
 BellmanFord
 FloydWarshall
 Johnson

2. Single Source ShortestPath in Linear Time 
Cornelius Diekmann
Slides, Paper 

3. Subcubic AllPairs Shortest Paths 
Anton Timofeev 

4. Spanners: Quality Measures and Efficient Construction 
Dmytro Traytel
Slides, Paper 

5. Distance Oracles: lower/upper space bounds 
N.N. 

6. Distance Labellings 
Stephan Matthias Günter
Slides, Paper 

7. Bidirectional Search and Goaldirected Dijkstra 
Alexander Kozyncev
Slides, Paper 

8. Bucket Levels 
N.N. 

9. Edge Reach & Highway Hierarchies 
N.N. 

10. Arc Flags 
Tobias Walter
Slides, Paper 

11. Transit Node Routing 
Andreas Heider
Slides, Paper 

12. Contraction Hierarchies 
Mykola Protsenko
Slides, Paper 
