1977/06/01 by M. R. Garey, David S. Johnson · 5 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Interconnection Networks and Systems #Computational Geometry and Mesh Generation #Steiner tree problem #Mathematics #Combinatorics #Heuristics #Tree (set theory) #Discrete mathematics #Graph #Polyomino #Plane (geometry) #Algorithm #Mathematical optimization #Geometry
paper · doi:10.1137/0132071
openalex publication_date 1977/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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 NP-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 NP-completeness of certain graph-theoretic problems are proved and may be of independent interest.