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] 
  • A. Berger, M. Grimmer and M. Müller-Hannemann. "Fully dynamic speed-up techniques for multi-criteria shortest paths searches in time-dependent networks". SEA 2010. P. Festa ed. 2010. pp. 35-46. [More] 
  • M. Müller-Hannemann and S. Schirra eds. Algorithm Engineering --- Bridging the gap between algorithm theory and practice. Springer, Heidelberg. 2010. [More] 
  • A. Berger and M. Müller-Hannemann. "Uniform Sampling of Directed Graphs with a Fixed Degree Sequence". Proceedings of WG 2010. 2010. pp. 220-231. [More] 
  • A. Berger and M. Müller-Hannemann. "Subpath-Optimality of Multi-Criteria Shortest Paths in Time- and Event-Dependent Networks". Institute of Computer Science, Martin-Luther-Universität Halle-Wittenberg. 2009. [More] 
  • M. Müller-Hannemann and M. Schnee. "Efficient Timetable Information in the Presence of Delays". Robust and Online Large-Scale Optimization. R. K. Ahuja, R. H. Möhring and C. D. Zaroliagis eds. 2009. pp. 249-272. [More] 
  • A. Berger, D. Delling, A. Gebhardt and M. Müller-Hannemann. "Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected". ATMOS 2009 - 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. J. Clausen and G. D. Stefano eds. 2009. [More] 
  • M. Schnee. "Fully realistic multi-criteria timetable information systems". Fachbereich Informatik, Technische Universität Darmstadt. 2009. [More] 
  • L. Frede, M. Müller-Hannemann and M. Schnee. "Efficient On-Trip Timetable Information in the Presence of Delays". ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. M. Fischetti and P. Widmayer eds. 2008. [More] 
  • Y. Disser, M. Müller-Hannemann and M. Schnee. "Multi-criteria Shortest Paths in Time-Dependent Train Networks". WEA. 2008. pp. 347-361. [More] 
View less
[ Back ]