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

Cooper, Colin; Frieze, Alan M.; Mehlhorn, Kurt; Priebe, Volker

doi:10.1007/3-540-63248-4_2

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

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

MPS-Authors

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45222

Priebe, Volker
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

https://rdcu.be/dwjJQ
(Publisher version)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

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 (Ed.), Randomization and Approximation Techniques in Computer Science (pp. 15-26). Berlin, Germany: Springer. doi:10.1007/3-540-63248-4_2.

Cite as: https://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.