The Rectilinear Steiner Tree Problem is -Complete
M. R. Garey, D. S. Johnson
Source abstract
An optimum rectilinear Steiner tree for a set A of points in the plane is a tree which interconnects A using horizontal and vertical lines of shortest possible total length. Such trees correspond to single net wiring patterns on printed backplanes which minimize total wire length. We show that the problem of determining this minimum length, given A, is -complete. Thus the problem of finding optimum rectilinear Steiner trees is probably computationally hopeless, and the emphasis of the literature for this problem on heuristics and special case algorithms is well justified. A number of intermediary lemmas concerning the -completeness of certain graph-theoretic problems are proved and may be of independent interest.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.