Add to Calendar
- Date:
- Fri, 2011-02-25 14:00 - 15:30
- Location:
- Klaus room 1447
- Cost:
- 0.00
We present a novel algorithm to solve the nonnegative single-source
shortest path problem on road networks and other graphs with low highway
dimension. After a quick preprocessing phase, we can compute all
distances from a given source in the graph with essentially a linear
sweep over all vertices. Because this sweep is independent of the
source, we are able to reorder vertices in advance to exploit locality.
Moreover, our algorithm takes advantage of features of modern CPU
architectures, such as SSE and multi-core.
