Finding a minimum weight K-link path in graphs with Monge property and applications

Abstract

Let G be a weighted, complete, directed acyclic graph (DAG), whose edge weights obey the 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 complexity of our algorithm is O(n√K log n) for the concave case and O(nα(n) log3 n) for the convex case. Our algorithm uses some properties of DAGs with Monge property together with a refined parametric search technique. We apply our algorithm (for the concave case) to get efficient solutions for the following problems, improving on previous results: (1) Finding the largest K-gon contained in a given polygon. (2) Finding the smallest K-gon that is the intersection of K halfplanes out of given set of halfplanes defining an n-gon. (3) Computing maximum K-cliques of an interval graph. (4) Computing length limited Huffman codes. (5) Computing optimal discrete quantization.