MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Meyer, Ulrichdblp
Editor(s):
BibTeX cite key*:
Meyer2001b
Title, Booktitle
Title*:
Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time
Booktitle*:
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)
Event, URLs
Conference URL::
http://www.siam.org/meetings/da01/
Downloading URL:
Event Address*:
Washington, DC
Language:
English
Event Date*
(no longer used):
January, 07-09
Organization:
ACM-SIAM
Event Start Date:
20 January 2021
Event End Date:
20 January 2021
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
797-806
Year*:
2001
VG Wort Pages:
30
ISBN/ISSN:
0-89871-490-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Keywords:
Shortest Path, Graph Algorithms, Average-Case Analysis
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Meyer2001b,
AUTHOR = {Meyer, Ulrich},
TITLE = {Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time},
BOOKTITLE = {Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)},
PUBLISHER = {ACM},
YEAR = {2001},
ORGANIZATION = {ACM-SIAM},
PAGES = {797--806},
ADDRESS = {Washington, DC},
MONTH = {January},
ISBN = {0-89871-490-7},
}


Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ulrich Meyer
Created
01/23/2001 03:34:10 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Anja Becker
Anja Becker
Ulrich Meyer
Ulrich Meyer
Ulrich Meyer
Edit Dates
22.03.2002 13:25:33
22.03.2002 13:16:18
08/01/2002 11:41:32
08/01/2002 11:29:54
08/01/2002 11:16:25