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

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)204-222
Number of pages19
JournalJournal of Algorithms
Volume29
Issue number2
DOIs
StatePublished - Nov 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Computing a Minimum Weight k-Link Path in Graphs with the Concave Monge Property'. Together they form a unique fingerprint.

Cite this