MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Meyer, Ulrich
Zeh, Norbert		dblp
dblp
Not MPG Author(s):
Zeh, Norbert
Editor(s):
Azar, Yossi
Erlebach, Thomas		dblp
dblp
Not MPII Editor(s):
Azar, Yossi
Erlebach, Thomas
BibTeX cite key*:
MeyZeh06
Title, Booktitle
Title*:
I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
Booktitle*:
Algorithms - ESA 2006, 14th Annual European Symposium
Event, URLs
Conference URL::
Downloading URL:
http://www.springerlink.com/content/m1211tt7726u8k12/fulltext.pdf
Event Address*:
Zurich, Switzerland
Language:
English
Event Date*
(no longer used):
Organization:
EATCS
Event Start Date:
11 September 2006
Event End Date:
13 September 2006
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4168
Number:
Month:
September
Pages:
540-551
Year*:
2006
VG Wort Pages:
19
ISBN/ISSN:
3-540-38875-3
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:

We show how to compute single-source shortest paths in undirected graphs with non-negative edge lengths in ${\mathcal{O}}(\sqrt{nm/B}\log n + {\mathit{MST}}(n,m))$I/Os, where n is the number of vertices, m is the number of edges, B is the disk block size, and MST(n,m) is the I/O-cost of computing a minimum spanning tree. For sparse graphs, the new algorithm performs ${\mathcal{O}}((n/\sqrt{B})\log n)$I/Os. This result removes our previous algorithm’s dependence on the edge lengths in the graph.
URL for the Abstract:
http://dx.doi.org/10.1007/11841036_49
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{MeyZeh06,
AUTHOR = {Meyer, Ulrich and Zeh, Norbert},
 EDITOR = {Azar, Yossi and Erlebach, Thomas},
 TITLE = {{I/O}-Efficient Undirected Shortest Paths with Unbounded Edge Lengths},
 BOOKTITLE = {Algorithms - ESA 2006, 14th Annual European Symposium},
 PUBLISHER = {Springer},
 YEAR = {2006},
 ORGANIZATION = {EATCS},
 VOLUME = {4168},
 PAGES = {540--551},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Zurich, Switzerland},
 MONTH = {September},
 ISBN = {3-540-38875-3},
}

Entry last modified by Christine Kiesel, 02/07/2007
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)
Ulrich Meyer		Created
09/26/2006 10:39:57 AM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Christine Kiesel
Ulrich Meyer
Ulrich Meyer
Edit Dates
07.02.2007 18:03:49
07.02.2007 15:10:05
11/23/2006 10:19:08 AM
09/26/2006 10:39:57 AM