Algorithms for interval structures with applications

We present new algorithms for two problems on interval structures that arise in computer-aided manufacturing and in other areas. We give an O(Kn) time algorithm for the single-source K-link shortest path problem on an interval graph with n weighted vertices, and two O(n) time algorithms for a generalized version of the optimal color-spanning problem for n points on a real line, where each point is assigned one of m colors (m≤n). A standard approach for solving the K-link shortest path problem would take O(Kn2) time, and thus our result offers a linear time improvement. The previously best known algorithm for the optimal color-spanning problem in R1 takes O(n) time and space. We provide two algorithms for a generalized version of this problem in which each color must appear a specified minimum number of times. One of these two solutions is suitable for an online processing of the (streaming) input points; it uses O(m) working space for the ordinary one-dimensional optimal color-spanning problem. We also show several applications of our algorithms in computer-aided manufacturing and in other areas.