Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Maue, Jens
Sanders, Peter
Matijevic, Domagoj

dblp
dblp
dblp

Not MPG Author(s):

Sanders, Peter

Editor(s):

Alvarez, Carme
Serna, Maria J.

dblp
dblp

Not MPII Editor(s):

Alvarez, Carme
Serna, Maria J.

BibTeX cite key*:

MaueSandersMatijevic2006

Title, Booktitle

Title*:

Goal Directed Shortest Path Queries Using Precomputed Cluster Distances

Booktitle*:

Experimental Algorithms, 5th International Workshop, WEA 2006

Event, URLs

URL of the conference:

http://www.lsi.upc.edu/~wea/

URL for downloading the paper:

http://www.springerlink.com/content/k213227411158347/fulltext.pdf

Event Address*:

Cala Galdana, Menorca, Spain

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

24 May 2006

Event End Date:

27 May 2006

Publisher

Name*:

Springer

URL:

http://www.springer.com

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

4007

Number:


Month:


Pages:

316-327

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

3-540-34597-3

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

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.

URL for the Abstract:

http://dx.doi.org/10.1007/11764298_29

Keywords:

Shortest Paths, Preprocessing, Graph Algorithms



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

External Affiliations:

Universität Karlsruhe (TH)

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{MaueSandersMatijevic2006,
AUTHOR = {Maue, Jens and Sanders, Peter and Matijevic, Domagoj},
EDITOR = {Alvarez, Carme and Serna, Maria J.},
TITLE = {Goal Directed Shortest Path Queries Using Precomputed Cluster Distances},
BOOKTITLE = {Experimental Algorithms, 5th International Workshop, WEA 2006},
PUBLISHER = {Springer},
YEAR = {2006},
VOLUME = {4007},
PAGES = {316--327},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Cala Galdana, Menorca, Spain},
ISBN = {3-540-34597-3},
}


Entry last modified by Uwe Brahm, 01/20/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Jens Maue
Created
06/21/2006 12:16:49 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Uwe Brahm
Christine Kiesel
Jens Maue
Jens Maue
Jens Maue
Edit Dates
01/20/2009 07:25:15 PM
07.02.2007 17:59:44
06/21/2006 12:31:43 PM
06/21/2006 12:28:51 PM
06/21/2006 12:20:15 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section