Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Meyer, Ulrich dblp
 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
 URL of the conference: http://www.siam.org/meetings/da01/ URL for downloading the paper: Event Address*: Washington, DC Language: English Event Date* (no longer used): January, 07-09 Organization: ACM-SIAM Event Start Date: 22 September 2019 Event End Date: 22 September 2019

 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:

 (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},