Premium
Average‐case complexity of shortest‐paths problems in the vertex‐potential model
Author(s) -
Cooper Colin,
Frieze Alan,
Mehlhorn Kurt,
Priebe Volker
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(200001)16:1<33::aid-rsa3>3.0.co;2-0
Subject(s) - combinatorics , vertex (graph theory) , mathematics , random graph , shortest path problem , discrete mathematics , graph
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 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. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 33–46, 2000