Edges as nodes - A new approach to timetable information

Show simple item record

dc.identifier.uri http://dx.doi.org/10.15488/1470
dc.identifier.uri http://www.repo.uni-hannover.de/handle/123456789/1495
dc.contributor.author Beyersdorff, Olaf
dc.contributor.author Nebesov, Yevgen
dc.date.accessioned 2017-05-10T11:33:53Z
dc.date.available 2017-05-10T11:33:53Z
dc.date.issued 2009
dc.identifier.citation Beyersdorff, O.; Nebesov, Y.: Edges as nodes - A new approach to timetable information. In: OpenAccess Series in Informatics 12 (2009). DOI: https://doi.org/10.4230/OASIcs.ATMOS.2009.2147
dc.description.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. eng
dc.language.iso eng
dc.publisher Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
dc.relation.ispartof 9th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2009, September 10, 2009, Copenhagen
dc.relation.ispartofseries OpenAccess Series in Informatics 12 (2009)
dc.rights CC BY 3.0
dc.rights.uri https://creativecommons.org/licenses/by/3.0/
dc.subject Earliest arrival problem eng
dc.subject Minimum number of transfers problem eng
dc.subject Time-expanded model eng
dc.subject Timetable infomation eng
dc.subject Earliest arrival eng
dc.subject Linear-time algorithms eng
dc.subject Minimum number of transfers eng
dc.subject New approaches eng
dc.subject SIMPLE algorithm eng
dc.subject Time-expanded models eng
dc.subject Time-table information eng
dc.subject Timetable infomation eng
dc.subject Clustering algorithms eng
dc.subject Optimization eng
dc.subject Scheduling eng
dc.subject.ddc 621,3 | Elektrotechnik, Elektronik ger
dc.title Edges as nodes - A new approach to timetable information
dc.type article
dc.type conferenceObject
dc.type Text
dc.relation.issn 2190-6807
dc.relation.doi https://doi.org/10.4230/OASIcs.ATMOS.2009.2147
dc.bibliographicCitation.volume 12
dc.description.version publishedVersion
tib.accessRights frei zug�nglich


Files in this item

The following license files are associated with this item:

This item appears in the following Collection(s):

Show simple item record

 

Search the repository


Browse

My Account

Usage Statistics