Algorithm Engineering for Dynamic Graph Optimization Problems in Concrete Applications

Description

 

Prof. Matthias Müller-Hannemann; Martin-Luther-Universität Halle-Wittenberg;

Prof. Dr. Karsten Weihe; Technische Universität Darmstadt

 

Project website

 

In many applications of graph algorithms or graph optimization problems, the graphs or the instances undergo frequent small changes. A graph is called dynamic if it is changed by a sequence of change operations. The goal of dynamic graph algorithms is to recompute optimal solutions after updates faster than by resolving from scratch.

The focus of this project is on several concrete applications of dynamic graph optimization problems, in particular

  1. speed-up techniques for time-dependent multi-criteria shortest path problems in a dynamic scenario,
  2. real-time timetable information of train connections in case of delays caused by construction work, technical defects or other reasons,
  3. passenger-oriented delay management in public transport.

Using techniques of Algorithm Engineering we aim at closing the current gaps to practical solutions.

  
  

Publications

  • T. Gunkel, M. Schnee and M. Müller-Hannemann. "How to find good night train connections", Networks, Vol. 57. 2011, pp. 19-27. [More] 
  • A. Berger, C. Blaar, A. Gebhardt, M. Müller-Hannemann and M. Schnee. "Passenger-oriented Train Disposition". Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg. Tech. Rep. 2011/2. 2011. [More] 
  • A. Berger, A. Gebhardt, M. Müller-Hannemann and M. Ostrowski. "Stochastic Delay Prediction in Large Train Networks". Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg. Tech. Rep. 2011/1. 2011. [More] 
  • M. Goerigk, M. Knoth, M. Müller-Hannemann, A. Schöbel and M. Schmidt. "The Price of Robustness in Timetable Information". Institut für Informatik, Martin-Luther-Universität Halle-Wittenberg. Tech. Rep. 2011/3. 2011. [More] 
  • A. Berger, M. Müller-Hannemann, S. Rechner and A. Zock. "Efficient Computation of Time-Dependent Centralities in Air Transportation Networks". WALCOM 2011. 2011. pp. 77-88. [More] 
View All
[ Back ]