| ID:
314436.0,
MPI für Informatik / Algorithms and Complexity Group |
| I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths |
| Authors: | Meyer, Ulrich; Zeh, Norbert |
| Editors: | Azar, Yossi; Erlebach, Thomas |
| Language: | English |
| Publisher: | Springer |
| Place of Publication: | Berlin, Germany |
| Date of Publication (YYYY-MM-DD): | 2006 |
| Title of Proceedings: | Algorithms - ESA 2006, 14th Annual European Symposium |
| Start Page: | 540 |
| End Page: | 551 |
| Title of Series: | Lecture Notes in Computer Science |
| Place of Conference/Meeting: | Zurich, Switzerland |
(Start) Date of Conference/Meeting
(YYYY-MM-DD): | 2006-09-11 |
| Audience: | Experts Only |
| Intended Educational Use: | No |
| Abstract / Description: | We show how to compute single-source shortest paths in undirected graphs with
non-negative edge lengths in 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 I/Os. This result removes our previous algorithm’s dependence on the
edge lengths in the graph. |
| Last Change of the Resource (YYYY-MM-DD): | 2007-02-10 |
| External Publication Status: | published |
| Document Type: | Conference-Paper |
| Communicated by: | Kurt Mehlhorn |
| Affiliations: | MPI für Informatik/Algorithms and Complexity Group
|
| Identifiers: | LOCALID:C1256428004B93B8-ABF03BBA009BE850C12571F5002F9A7D-...
ISBN:3-540-38875-3 |
|
Advanced
