✦ LIBER ✦

Average-case complexity of shortest-paths problems in the vertex-potential model

✍ Scribed by Colin Cooper; Alan Frieze; Kurt Mehlhorn; Volker Priebe

Publisher: John Wiley and Sons
Year: 2000
Tongue: English
Weight: 146 KB
Volume: 16
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(200001)16:1<33::aid-rsa3>3.0.co;2-0

No coin nor oath required. For personal study only.

✦ Synopsis

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 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.

📜 SIMILAR VOLUMES

The time-dependent shortest pair of disj

The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms

✍ Sherali, Hanif D.; Ozbay, Kaan; Subramanian, Shivaram 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 2 views

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issu