## 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 n2^{o(√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.

Original language | English (US) |
---|---|

Pages (from-to) | 204-222 |

Number of pages | 19 |

Journal | Journal of Algorithms |

Volume | 29 |

Issue number | 2 |

DOIs | |

State | Published - Nov 1998 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics