Computer Science – Data Structures and Algorithms
Scientific paper
2009-08-11
Computer Science
Data Structures and Algorithms
15 pages, technical report
Scientific paper
We successfully contract timetable networks with realistic transfer times. Contraction gradually removes nodes from the graph and adds shortcuts to preserve shortest paths. This reduces query times to 1 ms with preprocessing times around 6 minutes on all tested instances. We achieve this by an improved contraction algorithm and by using a station graph model. Every node in our graph has a one-to-one correspondence to a station and every edge has an assigned collection of connections. Our graph model does not need parallel edges. The query algorithm does not compute a single earliest arrival time at a station but a set of arriving connections that allow best transfer opportunities.
No associations
LandOfFree
Contraction of Timetable Networks with Realistic Transfers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Contraction of Timetable Networks with Realistic Transfers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Contraction of Timetable Networks with Realistic Transfers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-165161