Abstract
LetG 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-weightk-link path between a given pair of vertices for any givenk. The time complexity of our algorithm is\(O(n\sqrt {k\log n} + n\log n)\). Our algorithm uses some properties of DAGs with the concave Monge property together with the parametric search technique. We apply our algorithm to get efficient solutions for the following problems, improving on previous results: (1) Finding the largestk-gon contained in a given convex polygon. (2) Finding the smallestk-gon that is the intersection ofk half-planes out ofn half-planes defining a convexn-gon. (3) Computing maximumk-cliques of an interval graph. (4) Computing length-limited Huffman codes. (5) Computing optimal discrete quantization.
Article PDF
Similar content being viewed by others
References
A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric Applications of a Matrix-Searching Algorithm,Algorithmica 2 (1987), 195–208.
A. Aggarwal and J. Park, Notes on Searching in Multidimensional Monotone Arrays,Proc. 29th IEEE Symp. on Foundations on Computer Science, 1988, pp. 497–512.
A. Aggarwal and T. Tokuyama, Consecutive Interval Query and Dynamic Programming on Intervals,Proc. 4th Internat. Symp. on Algorithms and Computing, 1993, pp. 466–475. Lecture Notes in Computer Science, Vol. 762. Springer-Verlag, Berlin.
T. Asano, Dynamic Programming on Intervals,Proc. 2nd Internat. Symp. on Algorithms, 1991, pp. 199–207. Lecture Notes in Computer Science, Vol. 557. Springer-Verlag, Berlin.
W. Bein, L. Larmore, and J. Park, Thed-Edge Shortest-Path Problem for a Monge Graph, Preprint, 1992.
J. Boyce, D. Dobkin, R. Drysdale, and L. Guibas, Finding Extremal Polygons,SIAM J. Comput. 14 (1985), 134–147.
K. Chan and T. Lam, Finding Least-Weight Subsequences with Fewer Processors,Proc. SIGAL Internat. Symp. on Algorithms, 1990, pp. 318–327. Lecture Notes in Computer Science, Vol. 450. Springer-Verlag, Berlin.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, Diameter, Width, Closest Line Pair, and Parametric Searching,Proc. 8th ACM Symp. on Computational Geometry, 1992, pp. 120–129.
R. Cole, Slowing Down Sorting Networks to Obtain Faster Sorting Algorithms,J. Assoc. Comput. Mach. 34 (1987), 200–208.
G. Frederickson, Optimal Algorithms for Tree Partitioning,Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 1991, pp. 168–177.
M. Klawe, A Simple Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming, Technical Report 89-16, University of British Columbia, Vancouver, 1989.
M. Klawe and D. Kleitman, An Almost Linear-Time Algorithm for Generalized Matrix Searching, Technical Report RJ6275, IBM Almaden Research Center, 1988.
C. P. Kruskal, Searching, Merging and Sorting in Parallel Computation,IEEE Trans. Comput. 32 (1983), 942–946.
L. Larmore and D. Hirschberg, Length-Limited Coding,Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 310–318.
L. Larmore and T. Przytycka, Parallel Construction of Trees with Optimal Weighted Path Length,Proc. 3rd ACM Symp. on Parallel Algorithms and Architectures, 1991, pp. 71–80.
L. Larmore and B. Schieber, On-Line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure,J. Algorithms 12 (1991), 490–515.
N. Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms,J. Assoc. Comput. Mach. 30 (1983), 852–865.
R. Wilber, The Concave Least Weight Subsequence Problem Revisited,J. Algorithms 9 (1988), 418–425.
X. Wu, Optimal Quantization by Matrix Searching,J. Algorithms 12 (1991), 663–673.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Aggarwal, A., Schieber, B. & Tokuyama, T. Finding a minimum-weightk-link path in graphs with the concave Monge property and applications. Discrete Comput Geom 12, 263–280 (1994). https://doi.org/10.1007/BF02574380
Received:
Revised:
Published:
Issue date:
DOI: https://doi.org/10.1007/BF02574380