Computing optimal rectilinear Steiner trees: A survey and experimental evaluation

The rectilinear Steiner tree problem is to find a minimum-length rectilinea r interconnection of a set of points in the plane. A reduction from the rec tilinear Steiner tree problem to the graph Steiner tree problem allows the use of exact algorithms for the graph Steiner tree problem to solve the rec tilinear problem. Furthermore, a number of more direct, geometric algorithm s have been devised for computing optimal rectilinear Steiner trees. This p aper surveys algorithms for computing optimal rectilinear Steiner trees and presents experimental results comparing nine of them: graph Steiner tree a lgorithms due to Beasley, Bern, Dreyfus and Wagner, Hakimi, and Shore, Foul ds, and Gibbons and geometric algorithms due to Ganley and Cohoon, Salowe a nd Warme, and Thomborson, Alpern, and Carter. (C) 1999 Elsevier Science B.V . All rights reserved.