Average-case complexity of shortest-path
โ
Colin Cooper; Alan Frieze; Kurt Mehlhorn; Volker Priebe
๐
Article
๐
2000
๐
John Wiley and Sons
๐
English
โ 146 KB
๐ 2 views
We study the average-case complexity of shortest-paths problems in the vertexpotential model. The vertex-potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and wit