TY - GEN

T1 - Finding a minimum weight K-link path in graphs with Monge property and applications

AU - Aggarwal, Alok

AU - Schieber, Baruch

AU - Tokuyama, Takeshi

PY - 1993

Y1 - 1993

N2 - Let G be a weighted, complete, directed acyclic graph (DAG), whose edge weights obey the 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 O(n√K log n) for the concave case and O(nα(n) log3 n) for the convex case. Our algorithm uses some properties of DAGs with Monge property together with a refined parametric search technique. We apply our algorithm (for the concave case) to get efficient solutions for the following problems, improving on previous results: (1) Finding the largest K-gon contained in a given polygon. (2) Finding the smallest K-gon that is the intersection of K halfplanes out of given set of halfplanes defining an n-gon. (3) Computing maximum K-cliques of an interval graph. (4) Computing length limited Huffman codes. (5) Computing optimal discrete quantization.

AB - Let G be a weighted, complete, directed acyclic graph (DAG), whose edge weights obey the 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 O(n√K log n) for the concave case and O(nα(n) log3 n) for the convex case. Our algorithm uses some properties of DAGs with Monge property together with a refined parametric search technique. We apply our algorithm (for the concave case) to get efficient solutions for the following problems, improving on previous results: (1) Finding the largest K-gon contained in a given polygon. (2) Finding the smallest K-gon that is the intersection of K halfplanes out of given set of halfplanes defining an n-gon. (3) Computing maximum K-cliques of an interval graph. (4) Computing length limited Huffman codes. (5) Computing optimal discrete quantization.

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

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

U2 - 10.1145/160985.161135

DO - 10.1145/160985.161135

M3 - Conference contribution

AN - SCOPUS:0027802231

SN - 0897915828

SN - 9780897915823

T3 - Proceedings of the 9th Annual Symposium on Computational Geometry

SP - 189

EP - 197

BT - Proceedings of the 9th Annual Symposium on Computational Geometry

PB - Publ by ACM

T2 - Proceedings of the 9th Annual Symposium on Computational Geometry

Y2 - 19 May 1993 through 21 May 1993

ER -