Groupe d’études et de recherche en analyse des décisions


Heuristics for the Minimum Rec-tilinear Steiner Tree Problem: New Algorithms and a Computational Study


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.

, 22 pages

Ce cahier a été révisé en mars 1991