An Improved Exact Algorithm for the Euclidean k-Steiner Tree Problem

In the classical geometric Steiner tree problem, we are given a set of points in the plane and our aim is to find the shortest network interconnecting the set of points. An unlimited number of additional vertices, called Steiner points, may be added to shorten the network. In the minimum k -Steiner tree problem, the number of Steiner points is limited to some nonnegative integer k , which creates additional complexity. This paper improves on the current algorithmic approach to solving the Euclidean k -Steiner tree problem. We introduce a novel pruning test and strengthen existing tests to allow more extensive elimination of sub-optimal topologies during the generation phase of the algorithm. We also introduce a new ILP model for the concatenation phase. Finally, we present experimental results that demonstrate the effectiveness of these novel components.