Computing a minimum-weight κ-link path in graphs with the concave monge property

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 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 κ-link path between a given pair of vertices for any given κ. The algorithm runs in n2O(√logκloglogn) 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 κ-chques of an interval graph. (4) finding the largest κ-gon contained in a given convex polygon. (5) finding the smallest κ-gon that is the intersection of κ half-planes out of n half-planes defining a convex n-gon.

Original languageEnglish (US)
Title of host publicationProceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PublisherAssociation for Computing Machinery
Pages405-411
Number of pages7
ISBN (Electronic)0898713498
StatePublished - Jan 22 1995
Externally publishedYes
Event6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States
Duration: Jan 22 1995Jan 24 1995

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
CountryUnited States
CitySan Francisco
Period1/22/951/24/95

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Computing a minimum-weight κ-link path in graphs with the concave monge property'. Together they form a unique fingerprint.

Cite this