×

New pruning rules for the Steiner tree problem and 2-connected Steiner network problem. (English) Zbl 1453.68201

Summary: 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.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68R10 Graph theory (including graph drawing) in computer science

Software:

GeoSteiner
Full Text: DOI

References:

[1] Brazil, M.; Volz, M.; Zachariasen, M.; Ras, C.; Thomas, D. A., Computing minimum 2-edge-connected Steiner networks in the Euclidean plane, Networks, 1-15, (2018)
[2] Brazil, M.; Zachariasen, M., Optimal Interconnection Trees in the Plane, (2015), Springer International: Springer International Switzerland · Zbl 1319.05044
[3] Gilbert, E. N.; Pollak, H. O., Steiner minimal trees, SIAM J. Appl. Math., 16, 1-29, (1968) · Zbl 0159.22001
[4] Hvam, K.; Reinhardt, L.; Winter, P.; Zachariasen, M., Bounding component sizes of two-connected Steiner networks, Inf. Process. Lett., 104, 159-163, (2007) · Zbl 1190.90088
[5] Hvam, K.; Reinhardt, L.; Winter, P.; Zachariasen, M., Some structural and geometric properties of two-connected Steiner networks, (Computing: the Australasian Theory Symposium, CATS2007, Ballarat, Australia, Conferences in Research and Practice in Information Technology (CRPIT), vol. 65, (2007)) · Zbl 1190.90088
[6] Hwang, F. K.; Richards, D. S.; Winter, P., The Steiner Tree Problem, (1992), Elsevier · Zbl 0774.05001
[7] Juhl, D.; Warme, D. M.; Winter, P.; Zachariasen, M., The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study, Math. Program. Comput., 10, 487-532, (2018) · Zbl 1411.90225
[8] Luebke, E. L.; Provan, J. S., On the structure and complexity of the 2-connected Steiner network problem in the plane, Oper. Res. Lett., 26, 111-116, (2000) · Zbl 0960.05039
[9] Warme, D. M.; Winter, P.; Zachariasen, M., Exact algorithms for plane Steiner tree problems: a computational study, (Du, D.-Z.; Smith, J. M.; Rubinstein, J. H., Advances in Steiner Trees, (2000), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 81-116 · Zbl 0968.90067
[10] Winter, P.; Zachariasen, M., Euclidean minimum Steiner trees: an improved exact algorithm, Networks, 30, 149-166, (1997) · Zbl 0893.90170
[11] Winter, P.; Zachariasen, M., Two-connected Steiner networks: structural properties, Oper. Res. Lett., 33, 395-402, (2005) · Zbl 1090.90021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.