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
N1 - Funding Information:
G. P. and P. N. S. acknowledge the financial support offered by the A*Star (Agency for Science, Technology and Research). K. K. K. acknowledges Mr. Rajeev Gan-gal, CEO, Insilico division, Systems Biology India Pvt Ltd, Maharashtra, India for providing various resources to accomplish this research work and Prof. Thomas Martinetz and Dr. Stefen Moller, Institute for Neuro-and Bioinformatics, University of Luebeck, Germany for their support and critical reading of the manuscript.
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 -