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

                        Baruch Schieber
                    IBM -- Research Division
               T.J. Watson Research Center
            P.O. Box 218, Yorktown Heights, NY 10598.
                     sbar@watson.ibm.com

 Let  G  be  a weighted, complete, directed acyclic graph (DAG) 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
 n2^O(sqrt{log k loglog n}) time.  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.