Martin Luther University Halle-Wittenberg


Prof. Dr. Matthias Müller-Hannemann

phone: +49-345-5524729
fax: ++49-345-5527039

room 4.19
Institut für Informatik
Von-Seckendorffplatz 1
06120 Halle (Saale)

annabell.berger AT

Further settings

Login for editors

Dynamic Graph Optimization Problems

Project: Algorithm Engineering for Dynamic Graph Optimization Problems in Concrete Applications
(supported within research cluster 1307 of DFG)

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) real-time timetable information of train connections in case of delays caused by construction work, technical defects or other reasons,
(2) route planning in road networks with  time-dependent  driving speed.

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


Summary of Results

  • Real-time train information with dynamic updates
    We developed a fully realistic prototype for real-time timetable information subject to frequent updates due to delays and disturbances (Müller-Hannemann and Schnee 2009).
  • Multi-criteria train timetable information in time-dependent networks
    Several speed-up techniques for multi-criteria time-dependent shortest paths in a static scenario have been analyzed. We are able to explain why we can expect only marginal speed-ups (compared to observations in road networks) in timetable information of train networks by these techniques (ATMOS 2009).
  • Speed-up techniques for multi-criteria shortest paths with dynamic updates
    For dynamic updates we have developed two new speed-up techniques, one based on a specific substructure property of time-dependent paths, the other on so-called k-flags, an extension of arc flags (SEA 2010).
  • Robust timetable information
    We considered several notions of robustness in timetable information for public transport. Strict robustness turned out to be NP-hard, but conservative approximations can be computed in polynomial time. Based on the schedule of high-speed trains within Germany of 2011, we explore the trade-off between the level of guaranteed robustness and the increase in travel time (ATMOS 2011).
  • Passenger-oriented disposition and dynamic updates of passenger flows
    We have developed a model for passenger-friendly train disposition. This leads to dynamic passenger flow and optimization problems for which we implemented an efficient prototype (ESA 2011).
  • Stochastic propagation of delays
    We have implemented and tested a stochastic model for delay propagation and forecasts of arrival and departure events which is applicable to all kind of schedule-based public transport in an online real-time scenario (ATMOS 2011).
  • Time-dependent centrality
    We proposed new time-dependent centrality indices for network analysis and efficient algorithms for their computation. A case study with the worldwide air traffic network yields valuable insights into the ranking and competitiveness of airports (WALCOM 2011).
  • Uniform sampling of digraphs
    Uniformly sampling of digraphs with prescribed degree sequence is an important problem in complex network analysis. We have been able to show why a popular Markov chain based switching algorithm fails in general to sample uniformly at random but characterize under which efficiently checkable conditions it will provably succeed and how the general case can be solved (WG 2010).