New pruning rules for the Steiner tree problem and 2-connected Steiner network problem
Marcus Brazil, Marcus Volz, Martin Zachariasen, Charl Ras, Doreen Thomas
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | ELSEVIER SCIENCE BV | Published : 2019
We introduce the concepts of k-lunes and k-lune inequalities, which form the basis for new geometric pruning rules for limiting the number of candidate full components that need to be considered when solving the Euclidean Steiner tree problem or the Euclidean 2-connected Steiner network problem. For the latter problem, these new pruning rules constitute the first empty region properties to have been developed for the problem. We show how to implement these rules efficiently and run computational experiments, indicating the extent to which they can improve the performance of state-of-the-art algorithms for these problems.
Related Projects (1)
Awarded by Australian Research Council
This work was supported by the Australian Research Council [grant number DP160100639].