Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2007.1169
URN: urn:nbn:de:0030-drops-11695
URL: https://drops.dagstuhl.de/opus/volltexte/2007/1169/
Bauer, Reinhard ; Delling, Daniel ; Wagner, Dorothea
14. Experimental Study on Speed-Up Techniques for Timetable Information Systems
| pdf-format: |
|
Abstract
During the last years, impressive speed-up techniques for Dijkstra's algorithm have been developed. Unfortunately, recent research mainly focused on road networks. However, fast algorithms are also needed for other applications like timetable information systems. Even worse, the adaption of recently developed techniques to timetable information is often more complicated than expected.In this work, we check whether results from road networks are transferable to timetable information. To this end, we present an extensive experimental study of the most prominent speed-up techniques on different types of inputs. It turns out that recently developed techniques are much slower on graphs derived from timetable information than on road networks. In addition, we gain amazing insights into the behavior of speed-up techniques in general.
BibTeX - Entry
@InProceedings{bauer_et_al:OASIcs:2007:1169,
author = {Reinhard Bauer and Daniel Delling and Dorothea Wagner},
title = {{14. Experimental Study on Speed-Up Techniques for Timetable Information Systems}},
booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-939897-04-0},
ISSN = {2190-6807},
year = {2007},
volume = {7},
editor = {Christian Liebchen and Ravindra K. Ahuja and Juan A. Mesa},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1169},
URN = {urn:nbn:de:0030-drops-11695},
doi = {10.4230/OASIcs.ATMOS.2007.1169},
annote = {Keywords: Speed-up techniques, timetable information, shortest path}
}
| Keywords: | Speed-up techniques, timetable information, shortest path | |
| Seminar: | 7th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'07) | |
| Issue date: | 2007 | |
| Date of publication: | 06.11.2007 |
