Computing minimum 2-edge-connected Steiner networks in the Euclidean plane
Marcus Brazil, Marcus Volz, Martin Zachariasen, Charl Ras, Doreen Thomas
NETWORKS | WILEY | Published : 2019
We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2-edge-connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2-edge-con..View full abstract
Related Projects (1)
Awarded by Australian Research Council
This research was supported by the Australian Research Council, DP160100639.