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

DOI10.1007/BF01582073MaRDI QIDQ1327560zbMATH OpenFDO

Authors Edmund Ihler

Publication date 17 April 1995

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01582073

zbMATH Keywords

rectilinear Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 512925
• On exact solutions for the rectilinear Steiner tree problem. I: Theoretical results
• Class Steiner trees and VLSI-design
• Subclass of the Steiner problems on a plane with rectilinear metric
• scientific article; zbMATH DE number 8006

Cites work

• Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
• scientific article; zbMATH DE number 4191148 (Why is no real title available?)
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 139784 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 194508 (Why is no real title available?)
• scientific article; zbMATH DE number 219235 (Why is no real title available?)
• On Steiner’s Problem with Rectilinear Distance
• Rectilinear steiner trees: Efficient special-case algorithms
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(3)

• Class Steiner trees and VLSI-design
• A catalog of Hanan grid problems
• scientific article; zbMATH DE number 512925 (Why is no real title available?)

This page was built for publication: The rectilinear class Steiner tree problem for intervals on two parallel lines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1327560)