TY - GEN

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

AU - Schieber, Baruch

PY - 1995/1/22

Y1 - 1995/1/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0037784118&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037784118&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0037784118

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 405

EP - 411

BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

PB - Association for Computing Machinery

T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

Y2 - 22 January 1995 through 24 January 1995

ER -