### 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.

report47.ps.gz