Contraction of Timetable Networks with Realistic Transfers

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-165161

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.