English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time

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.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Meyer, Ulrich1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022001
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : ACM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518105
Other: Local-ID: C1256428004B93B8-DF1C429F0274A201C12569DD00500891-Meyer2001b
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Washington, DC
Start-/End Date: 2001

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-01)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, USA : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 797 - 806 Identifier: ISBN: 0-89871-490-7