Finding a minimum-weight k-link path in graphs with the concave Monge property and applications

A. Aggarwal, B. Schieber, T. Tokuyama

Research output: Contribution to journalArticlepeer-review

65 Scopus citations

Abstract

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 time complexity of our algorithm is {Mathematical expression}. Our algorithm uses some properties of DAGs with the concave Monge property together with the parametric search technique. We apply our algorithm to get efficient solutions for the following problems, improving on previous results: (1) Finding the largest k-gon contained in a given convex polygon. (2) Finding the smallest k-gon that is the intersection of k half-planes out of n half-planes defining a convex n-gon. (3) Computing maximum k-cliques of an interval graph. (4) Computing length-limited Huffman codes. (5) Computing optimal discrete quantization.

Original languageEnglish (US)
Pages (from-to)263-280
Number of pages18
JournalDiscrete & Computational Geometry
Volume12
Issue number1
DOIs
StatePublished - Dec 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Finding a minimum-weight k-link path in graphs with the concave Monge property and applications'. Together they form a unique fingerprint.

Cite this