About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SCG 1993
Conference paper
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.