Edges as nodes - A new approach to timetable information

Abstract

In this paper we suggest a new approach to timetable information by introducing the "edge-converted graph" of a timetable. Using this model we present simple algorithms that solve the earliest arrival problem (EAP) and the minimum number of transfers problem (MNTP). For constant-degree graphs this yields linear-time algorithms for EAP and MNTP which improves upon the known DIJKSTRA-based approaches. We also test the performance of our algorithms against the classical algorithms for EAP and MNTP in the time-expanded model.