ALCOMFT-TR-02-70

Frank Schulz, Dorothea Wagner and Christos Zaroliagis
Using Multi-Level Graphs for Timetable Information in Railway Systems
Patras. Work packages 3 and 5. May 2002.

Abstract: 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.

Postscript file: ALCOMFT-TR-02-70.ps.gz (110 kb).