---

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.

Participants

• Prof. Dr. Matthias Müller-Hannemann (project leader)
• Prof. Dr. Karsten Weihe    (TU Darmstadt)
• M.Sc. Annabell Berger (funded by DFG grant)
• Dr. Mathias Schnee    (TU Darmstadt)

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).

Publications

• Annabell Berger, Christian Blaar, Andreas Gebhardt, Matthias Müller-Hannemann and Mathias Schnee
  Passenger Flow-Oriented Train Disposition, Proceedings of ESA 2011, Saarbrücken, LNCS 6942, pp. 227-238, Springer, Heidelberg. Full version: Technical Report 2011/2, Institut für Informatik, MLU Halle-Wittenberg
• Annabell Berger, Andreas Gebhardt, Matthias Müller-Hannemann and Martin Ostrowski:
  Stochastic Delay Prediction in Large Train Networks, ATMOS 2011, OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 100-111, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
• Marc Goerigk, Martin Knoth, Matthias Müller-Hannemann, Anita Schöbel and Marie Schmidt:
  The Price of Robustness in Timetable Information,
  ATMOS 2011, OpenAccess Series in Informatics (OASIcs), vol. 20, pp. 76-87, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
• Annabell Berger and Matthias Müller-Hannemann
  Dag Realizations of Directed Degree Sequences
  Proceedings of FCT 2011, Oslo, Norway, LNCS 6914, pp. 264-275, Springer, Heidelberg. Full version: Technical Report 2011/5, Institut für Informatik, MLU Halle-Wittenberg,
• Annabell Berger, Matthias Müller-Hannemann, Steffen Rechner, and Alexander Zock:
  Efficient Computation of Time-Dependent Centralities in Air Transportation Networks Proceedings of WALCOM 2011, LNCS 6552, pp. 77-88, Springer.
• Torsten Gunkel, Matthias Müller-Hannemann and Mathias Schnee:
  Improved Search for Night Train Connections, Networks 57(1), pp. 19-27 (2011).
• Annabell Berger, Martin Grimmer, and Matthias Müller-Hannemann:
  Fully dynamic speed-up techniques for multi-criteria shortest paths searches in time-dependent networks, Proceedings of SEA 2010, LNCS 6049, pages 35-46, Springer, 2010.
• Annabell Berger and Matthias Müller-Hannemann:
  Uniform Sampling of Undirected and Directed Graphs with a Fixed Degree Sequence, extended abstract in Proceedings of WG 2010, LNCS 6410, pp. 220-231, Springer, 2010.
• Annabell Berger, Daniel Delling, Andreas Gebhardt, and Matthias Müller-Hannemann:
  Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected,
  Proceedings of ATMOS 2009.
• Matthias Müller-Hannemann and Mathias Schnee:
  Efficient Timetable Information in the Presence of Delays, in Robust and Online Large Scale Optimization, LNCS 5868, pp. 249–272, Springer, 2009.
• Lennart Frede, Matthias Müller-Hannemann, and Mathias Schnee:
  Efficient On-Trip Timetable Information in the Presence of Delays, Proceedings of ATMOS 2008.
• Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee
  Multi-Criteria Shortest Paths in Time-Dependent Train Networks, in C.C. McGeoch (ed.): WEA 2008, LNCS 5038, pp. 347-361, 2008.

Up