English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths

MPS-Authors
/persons/resource/persons45038

Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45791

Zeh,  Norbert
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Meyer, U., & Zeh, N. (2006). I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths. In Algorithms - ESA 2006, 14th Annual European Symposium (pp. 540-551). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-233F-8
Abstract
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.