Computing a Minimum Weight k-Link Path in Graphs with the Concave Monge Property

Abstract

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 algorithm runs in n2o(√log k log n) time, for k = Ω(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 discrete 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. © 1998 Academic Press.