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