Campus Event Calendar
Event Entry
What and Who
Real Shortest Paths in Real Time
Holger Bast
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 4 April 2006
13:30
30 Minutes
E1 4
024
Saarbrücken
Abstract
Joint work with Domagoj and Stefan F. Work in progress with a nice idea and a nice demo.
It's about answering shortest path queries on (real) road networks in log n time, with an O(n) time and O(n) space preprocessing, where n is the number of nodes. These three bounds have not been simultaneously attained so far.
The constants are such that for the road map of Germany (about 4 million nodes) query times are below 1 millisecond, and preprocessing takes a couple of hours using about 2 GB of main memory of a standard PC. In comparison, a standard Dijkstra computation for this map takes a couple of seconds.
Contact
Holger Bast
--email hidden
passcode not visible
logged in users only
Holger Bast, 04/04/2006 01:58
Holger Bast, 04/03/2006 11:15 -- Created document.
Holger Bast, 04/03/2006 11:15 -- Created document.