D-edge shortest-path problem for a Monge graph

摘要

A complete edge-weighted directed graph on vertices 1,2,...,n that assigns cost c(i,j) to the edge (i,j) is called Monge if its edge costs form a Monge array, i.e., for all i 0 for all i and j, our algorithm runs in O(n(1 + 1g(U/L))) time. Thus, when d (much gt) 1 + 1g(U/L), our algorithm represents a significant improvement over Aggarwal et al.'s O(dn)-time algorithm. We also present several applications of our algorithm; they include length-limited Huffman coding, finding the maximum-perimeter d-gon inscribed in a given convex n-gon, and a digital-signal-compression problem.