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 ( K n ) 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 ( K n 2 ) time, and thus our result offers a linear time improvement. The previously best known algorithm for the optimal color-spanning problem in R 1 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.

Authors

• Danny Z. Chen University of Notre Dame
• Ewa Misiołek

Keywords

No keywords are indexed for this paper.