Pregled bibliografske jedinice broj: 323878
Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
Goal Directed Shortest Path Queries Using Precomputed Cluster Distances // Experimental Algorithms, 5th International Workshop, WEA 2006 / Alvarez, Carme ; Serna, Maria J. (ur.).
Berlin: Springer, 2006. str. 316-327 (predavanje, međunarodna recenzija, cjeloviti rad (in extenso), znanstveni)
CROSBI ID: 323878 Za ispravke kontaktirajte CROSBI podršku putem web obrasca
Naslov
Goal Directed Shortest Path Queries Using Precomputed Cluster Distances
Autori
Maue, Jens ; Sanders, Peter ; Matijević, Domagoj
Vrsta, podvrsta i kategorija rada
Radovi u zbornicima skupova, cjeloviti rad (in extenso), znanstveni
Izvornik
Experimental Algorithms, 5th International Workshop, WEA 2006
/ Alvarez, Carme ; Serna, Maria J. - Berlin : Springer, 2006, 316-327
ISBN
3-540-34597-3
Skup
5th International Workshop on Experimetal Algorithms (WEA 2006),
Mjesto i datum
Menorca, Španjolska, 24.05.2006. - 27.05.2006
Vrsta sudjelovanja
Predavanje
Vrsta recenzije
Međunarodna recenzija
Ključne riječi
shortest paths
Sažetak
We demonstrate how Dijkstra's algorithm for shortest path queries can be accelerated by using precomputed shortest path distances. Our approach allows a completely flexible tradeoff between query time and space consumption for precomputed distances. In particular, sublinear space is sufficient to give the search a strong ``sense of direction''. We evaluate our approach experimentally using large, real-world road networks.
Izvorni jezik
Engleski
Znanstvena područja
Računarstvo
POVEZANOST RADA
Projekti:
235-2352818-1034 - Nelinearni problemi procjene parametara u matematičkim modelima (Jukić, Dragan, MZOS ) ( CroRIS)
Ustanove:
Sveučilište u Osijeku, Odjel za matematiku
Profili:
Domagoj Matijević
(autor)
