Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear 
Average-Case Time

Meyer, Ulrich

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time

MPS-Authors

/persons/resource/persons45038

Meyer, Ulrich
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. (2001). Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01) (pp. 797-806). New York, USA: ACM.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-31BB-8

Abstract

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 a simple algorithm for arbitrary directed graphs with random edge weights uniformly distributed in $\left[0,1\right]$ and show that it needs linear time ${\cal O}(n+m)$ with high probability.