𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The monotonic diameter of the perfect matching and shortest path polytopes

✍ Scribed by Fred J Rispoli

Book ID
107918216
Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
327 KB
Volume
12
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The complexity of shortest path and dila
The complexity of shortest path and dilation bounded interval routing
✍ Rastislav KrΓ‘ΔΎovič; Peter RuΕΎička; Daniel Ε tefankovič πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 227 KB

Interval routing is a popular compact routing method for point-to-point networks which found industrial applications in novel transputer routing technology (May and Thompson, Transputers and Routers: Components for Concurrent Machines, Inmos, 1991). Recently much e ort is devoted to relate the e ci

On the all-pairs shortest-path algorithm
On the all-pairs shortest-path algorithm of Moffat and Takaoka
✍ Kurt Mehlhorn; Volker Priebe πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 213 KB πŸ‘ 3 views

We review how to solve the all-pairs shortest-path problem in a nonnegatively Ε½ 2 . weighted digraph with n vertices in expected time O n log n . This bound is shown to hold with high probability for a wide class of probability distributions on nonnegatively weighted Ε½ . digraphs. We also prove that