English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

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;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
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: http://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.