License: 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.2008.1582
URN: urn:nbn:de:0030-drops-15826
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1582/
Go to the corresponding OASIcs Volume Portal

Delling, Daniel ; Pajor, Thomas ; Wagner, Dorothea

Engineering Time-Expanded Graphs for Faster Timetable Information

pdf-format:
08002.Delling.1582.pdf (0.2 MB)

Abstract

We present an extension of the well-known time-expanded approach
for timetable information. By remodeling unimportant stations, we are able to
obtain faster query times with less space consumption than the original model.
Moreover, we show that our extensions harmonize well with speed-up techniques
whose adaption to timetable networks is more challenging than one might expect.

BibTeX - Entry

@InProceedings{delling_et_al:OASIcs:2008:1582,
  author =	{Daniel Delling and Thomas Pajor and Dorothea Wagner},
  title =	{{Engineering Time-Expanded Graphs for Faster Timetable Information}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) },
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Matteo Fischetti and Peter Widmayer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1582},
  URN =		{urn:nbn:de:0030-drops-15826},
  doi =		{10.4230/OASIcs.ATMOS.2008.1582},
  annote =	{Keywords: Timetable information, shortest path, modeling}
}

Keywords: Timetable information, shortest path, modeling
Collection: 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)
Issue Date: 2008
Date of publication: 24.09.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI