Finding a minimum weight K -link path in graphs with Monge property and applications
Alok Aggarwal, Baruch Schieber, Takashi Tokuyama · 1993
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~=) for the concave case and O (ncr (n) log3 n) for the convex case.Our algorithm uses some properties of DAGs withMonge 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 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.