Beyersdorff, O.; Nebesov, Y.: Edges as nodes - A new approach to timetable information. In: 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2009 (OpenAccess Series in Informatics ; 12), 2147. DOI:
https://doi.org/10.4230/OASIcs.ATMOS.2009.2147
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.
|
License of this version: |
CC BY 3.0 Unported - https://creativecommons.org/licenses/by/3.0/
|
Publication type: |
BookPart |
Publishing status: |
publishedVersion |
Publication date: |
2009 |
Keywords english: |
Earliest arrival problem, Minimum number of transfers problem, Time-expanded model, Timetable infomation, Earliest arrival, Linear-time algorithms, Minimum number of transfers, New approaches, SIMPLE algorithm, Time-expanded models, Time-table information, Timetable infomation, Clustering algorithms, Optimization, Scheduling
|
DDC: |
621,3 | Elektrotechnik, Elektronik
|
Controlled keywords(GND): |
Konferenzschrift
|