de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

On the All-Pairs Shortest-Path Algorithm of Moffat and Takaoka

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45222

Priebe,  Volker
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Mehlhorn, K., & Priebe, V. (1997). On the All-Pairs Shortest-Path Algorithm of Moffat and Takaoka. Random Structures Algorithms, 10, 205-220.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-38C4-F
Zusammenfassung
We review how to solve the all-pairs shortest-path problem in a non-negatively weighted digraph with $n$ vertices in expected time $O(n^2 \log n)$. This bound is shown to hold with high probability for a wide class of probability distributions on non-negatively weighted digraphs. We also prove that for a large class of probability distributions, $\Omega(n\log n)$ time is necessary with high probability to compute shortest-path distances with respect to a single source.