Technical Report No. 47, December 1993 - Abstract

Edmund Ihler:
The Rectilinear Class Steiner Tree Problem for Intervals on Two Parallel Lines

We consider a generalization of the Rectilinear Steiner Tree problem, where our input is classes of required points instead of simple required points. Our task is to find a minimum rectilinear tree connecting at least one point from each class. We prove that the version, where all required points lie on two parallel lines, called the Rectilinear Steiner Tree (channel) problem, is NP-hard. But we give a linear time algorithm for the case where the points of each required class are clustered, and the classes consist of non overlapping intervals of points.