OASIcs.ATMOS.2009.2147.pdf
- Filesize: 375 kB
- 12 pages
Document
Edges as Nodes - a New Approach to Timetable Information
Authors
-
Part of:
Volume:
9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (ATMOS 2009)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-11-25
Cite AsGet BibTex
Olaf Beyersdorff and Yevgen Nebesov. Edges as Nodes - a New Approach to Timetable Information. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/OASIcs.ATMOS.2009.2147
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 \emph{Dijkstra}-based approaches.
We also test the performance of our algorithms against the classical
algorithms for EAP and MNTP in the time-expanded model.
Keywords
- Timetable infomation
- earliest arrival problem
- minimum number of transfers problem
- time-expanded model Timetable infomation
- earliest arrival problem
- minimum number of transfers problem
- time-expanded model
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads