The rectilinear class Steiner tree problem for intervals on two parallel lines (Q1327560)

A generalization of the rectilinear Steiner tree problem is given, if the inputs are classes of required points instead of simple required points. The author regards the problem of finding a minimum rectilinear tree, connecting one point of each class. The version, where all points lie on two parallel lines is shown to be NP-hard (rectilinear class Steiner tree problem). The author presents an algorithm which works in linear time if a constant bounded vertical class cut is given (in general the problem is NP-hard). The algorithm is an extension of the algorithm for the classical rectilinear Steiner tree problem of Aho/Garey.