Oktay Günlük, Tracy Kimbrel, et al.
Transportation Science
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.
Oktay Günlük, Tracy Kimbrel, et al.
Transportation Science
Rohit Khandekar, Baruch Schieber, et al.
FSTTCS 2010
Samir Khuller, Baruch Schieber
Information Processing Letters
Guy Even, Retsef Levi, et al.
ACM Transactions on Algorithms