# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model

##### External Resource

No external resources are shared

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Cooper, C., Frieze, A. M., Mehlhorn, K., & Priebe, V. (1997). Average-Case Complexity
of Shortest-Paths Problems in the Vertex-Potential Model. In J. Rolim (*Randomization
and Approximation Techniques in Computer Science* (pp. 15-26). Berlin, Germany: Springer. doi:10.1007/3-540-63248-4_2.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-38CD-E

##### Abstract

We study the average-case complexity of shortest-paths problems in the
vertex-potential model. The vertex-potential model is a family of probability
distributions on
complete directed graphs with \emph{arbitrary} real edge lengths but
without negative cycles. We show that on a graph with $n$ vertices and
with respect to this model, the single-source shortest-paths problem can be
solved in $O(n^2)$
expected time, and the all-pairs shortest-paths problem can be solved in $O(n^2
\log n)$
expected time.