Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-2001-1-002

Directed single-source shortest-paths in linear average-case time

Meyer, Ulrich

MPI-I-2001-1-002. May 2001, 32 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
The quest for a linear-time single-source shortest-path (SSSP) algorithm
on
directed graphs with positive edge weights is an ongoing hot research
topic. While Thorup recently found an ${\cal O}(n+m)$ time RAM algorithm
for undirected graphs with $n$ nodes, $m$ edges and integer edge weights
in
$\{0,\ldots, 2^w-1\}$ where $w$ denotes the word length, the currently
best time bound for directed sparse graphs on a RAM is
${\cal O}(n+m \cdot \log\log n)$.

In the present paper we study the average-case complexity of SSSP.
We give simple label-setting and label-correcting algorithms for
arbitrary directed graphs with random real edge weights
uniformly distributed in $\left[0,1\right]$ and show that they
need linear time ${\cal O}(n+m)$ with high probability.
A variant of the label-correcting approach also supports
parallelization.
Furthermore, we propose a general method to construct graphs with
random edge weights which incur large non-linear expected running times on
many traditional shortest-path algorithms.


Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2001-1-002.ps409 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2001-1-002
Hide details for BibTeXBibTeX
@TECHREPORT{Ulrich2001,
  AUTHOR = {Meyer, Ulrich},
  TITLE = {Directed single-source shortest-paths in linear average-case time},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2001-1-002},
  MONTH = {May},
  YEAR = {2001},
  ISSN = {0946-011X},
}