Edges as Nodes - a New Approach to Timetable Information

Beyersdorff, Olaf; Nebesov, Yevgen

doi:10.4230/OASIcs.ATMOS.2009.2147

Document

Edges as Nodes - a New Approach to Timetable Information

Authors Olaf Beyersdorff, Yevgen Nebesov

Part of: Volume: 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (ATMOS 2009)
Part of: Series: Open Access Series in Informatics (OASIcs)
Part of: 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

PDF

File

PDF

OASIcs.ATMOS.2009.2147.pdf

Filesize: 375 kB
12 pages

Document Identifiers

DOI: 10.4230/OASIcs.ATMOS.2009.2147
URN: urn:nbn:de:0030-drops-21478

Subject Classification

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)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get 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

Author Details

Olaf Beyersdorff

Yevgen Nebesov

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail