All-pairs shortest paths in O(n2) time with high probability
METADATA ONLY
Loading...
Author / Producer
Date
2013-08
Publication Type
Journal Article
ETH Bibliography
no
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0,1] is O(n2), in expectation and with high probability. This resolves a long-standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano [2006]. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n2), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log2n) expected time.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
60 (4)
Pages / Article No.
26
Publisher
Association for Computing Machinery
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin