𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimum path partitioning—An illustration of the Monge property

✍ Scribed by Pei-Hao Ho; Arie Tamir; Bang Ye Wu


Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
121 KB
Volume
36
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.


📜 SIMILAR VOLUMES


Computing a Minimum Weightk-Link Path in
✍ Baruch Schieber 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 233 KB

Let G be a weighted, complete, directed acyclic graph whose edge weights obey the concave Monge condition. We give an efficient algorithm for finding the minimum weight k-link path between a given pair of vertices for any given k. The time, for k s ⍀ log n . Our algorithm can be applied to get effi