Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property
✍ Scribed by Baruch Schieber
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 233 KB
- Volume
- 29
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 efficient solutions for the following problems, improving on previous Ž . Ž . results: 1 computing length-limited Huffman codes, 2 computing optimal dis-Ž . Ž . crete quantization, 3 computing maximum k-cliques of an interval graph, 4
Ž . finding the largest k-gon contained in a given convex polygon, 5 finding the smallest k-gon that is the intersection of k half-planes out of n half-planes defining a convex n-gon.