Summary: We present a computational study of exact algorithms for the Euclidean and rectilinear Steiner tree problems in the plane. These algorithms – which are based on the generation and concatenation of full Steiner trees – are much more efficient than other approaches and allow exact solutions of problem instances with more than 2000 terminals. The full Steiner tree generation algorithms for the two problem variants share many algorithmic ideas and the concatenation part is identical (integer programming formulation solved by branch-and-cut). Performance statistics for randomly generated instances, public library instances and “difficult” instances with special structure are presented. Also, results on the comparative performance on the two problem variants are given.
For the entire collection see [Zbl 0932.00010].