We propose in this paper new approximate algorithms for the Minimum Rectilinear Steiner Tree problem, based on a two-point-connection strategy. We also present extensive computational experiments involving the new algorithms and several existing heuristics, more consistent than the other experiments reported in the literature. We conclude from these experiments that one of these new heuristics obtains slightly better solutions in the average when compared with the previously known heuristics.
Paru en juillet 1990 , 22 pages
Ce cahier a été révisé en mars 1991