research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleUsing Multi-Level Graphs for Timetable Information in Railway Systems
Bibtex cite IDRACTI-RU1-2002-21
Booktitle 4th Workshop on Algorithm Engineering and Experiments
Series Lecture Notes in Computer Science
Year published 2002
Month January
Volume 2409
Pages 43-59
Organization ALENEX 2002
Location San Francisco, California
In many fields of application, shortest path finding problems in very large graphs arise. Scenarios where large numbers of on-line queries for shortest paths have to be processed in real-time appear for example in traffic information systems. In such systems, the techniques considered to speed up the shortest path computation are usually based on precomputed information. One approach proposed often in this context is a space reduction, where precomputed shortest paths are replaced by single edges with weight equal to the length of the corresponding shortest path. In this paper, we give a first systematic experimental study of such a space reduction approach. We introduce the concept of multi-level graph decomposition. For one specific application scenario from the field of timetable information in public transport, we perform a detailed analysis and experimental evaluation of shortest path computations based on multi-level graph decomposition.
Schulz, Frank
Wagner, Dorothea
Zaroliagis, Christos
C27-alenex2002-mlg.pdf (main file)
Publication ID408