Algorithms for Euclidean degree bounded spanning tree problems. (English) Zbl 1430.68353
Summary: Given a set of points in the Euclidean plane, the Euclidean \(\delta\)-minimum spanning tree \((\delta\)-MST) problem is the problem of finding a spanning tree with maximum degree no more than \(\delta\) for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean \(\delta\)-minimum bottleneck spanning tree \((\delta\)-MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When \(\delta \leq 4\), these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
minimum spanning trees; bottleneck objective; heuristic algorithms; discrete geometry; bounded degree; combinatorial optimisationReferences:
| [1] | Graham, R. L. and Hell, P., On the history of the minimum spanning tree problem, Ann. History Comput.7 (1985) 43. · Zbl 0998.68003 |
| [2] | Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc.7 (1956) 48. · Zbl 0070.18404 |
| [3] | Prim, R. C., Shortest connection networks and some generalizations, Bell Syst. Tech. J.36 (1957) 1389. |
| [4] | Camerini, P. M., The min – max spanning tree problem and some extensions, Inf. Process. Lett.7 (1978) 10. · Zbl 0373.05028 |
| [5] | Monma, C. and Suri, S., Transitions in geometric minimum spanning trees, Discr. Comput. Geom.8 (1992) 265. · Zbl 0764.05022 |
| [6] | Papadimitriou, C. H. and Vazirani, U. V., On two geometric problems related to the travelling salesman problem, J. Algorithms5 (1984) 231. · Zbl 0551.90093 |
| [7] | Francke, A. and Hoffmann, M., The Euclidean degree-4 minimum spanning tree problem is NP-hard, in Proc. Twenty-Fifth Annual Symposium on Computational Geometry (ACM, 2009), pp. 179-188. · Zbl 1380.68197 |
| [8] | Andersen, P. J. and Ras, C. J., Minimum bottleneck spanning trees with degree bounds, Networks68 (2016) 302. · Zbl 1390.90088 |
| [9] | Khuller, S., Raghavachari, B. and Young, N., Low-degree spanning trees of small weight, SIAM J. Comput.25 (1996) 355. · Zbl 0849.05022 |
| [10] | Chan, T. M., Euclidean bounded-degree spanning tree ratios, in Proc. Nineteenth Annual Symposium on Computational Geometry (ACM, 2003), pp. 11-19. · Zbl 1374.68652 |
| [11] | Narula, S. C. and Ho, C. A., Degree-constrained minimum spanning tree, Comput. Operat. Res.7 (1980) 239. |
| [12] | Knowles, J. and Corne, D., A new evolutionary approach to the degree-constrained minimum spanning tree problem, IEEE Trans. Evolutionary Comput.4 (2000) 125. |
| [13] | Bui, T. N. and Zrncic, C. M., An ant-based algorithm for finding degree-constrained minimum spanning tree, in Proc. 8th Annual Conference on Genetic and Evolutionary Computation (ACM, 2006), pp. 11-18. |
| [14] | N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Technical report, DTIC Document, 1976. · Zbl 1489.90150 |
| [15] | Lin, S. and Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Operat. Res.21 (1973) 498. · Zbl 0256.90038 |
| [16] | Arora, S., Polynomial time approximation schemes for Euclidean TSP and other geometric problems, in Foundations of Computer Science, 1996. Proceedings, 37th Annual Symposium on (IEEE, 1996), pp. 2-11. |
| [17] | Mitchell, J. S. B., Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems, SIAM J. Comput.28 (1999) 1298. · Zbl 0940.68062 |
| [18] | Rosenkrantz, D. J., Stearns, R. E. and Lewis, P. M. II, An analysis of several heuristics for the traveling salesman problem, SIAM J. Comput.6 (1977) 563. · Zbl 0364.90104 |
| [19] | Laporte, G., The traveling salesman problem: An overview of exact and approximate algorithms, Eur. J. Operat. Res.59 (1992) 231. · Zbl 0760.90089 |
| [20] | Hoogeveen, J., Analysis of Christofides’ heuristic: Some paths are more difficult than cycles, Operat. Res. Lett.10 (1991) 291. · Zbl 0748.90071 |
| [21] | An, H.-C., Kleinberg, R. and Shmoys, D. B., Improving Christofides’ algorithm for the \(s - t\) path TSP, J. ACM (JACM)62 (2015) 34. · Zbl 1426.68300 |
| [22] | Traub, V. and Vygen, J., Approaching \(\frac{3}{2}\) for the \(s - t\) path TSP, in Proc. Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (Society for Industrial and Applied Mathematics, 2018), pp. 1854-1864. · Zbl 1403.68355 |
| [23] | Parker, R. G. and Rardin, R. L., Guaranteed performance heuristics for the bottleneck travelling salesman problem, Operat. Res. Lett.2 (1984) 269. · Zbl 0528.90084 |
| [24] | Steele, J. M., Shepp, L. A. and Eddy, W. F., On the number of leaves of a Euclidean minimal spanning tree, J. Appl. Probab.24 (1987) 809. · Zbl 0639.60014 |
| [25] | Jothi, R. and Raghavachari, B., Degree-bounded minimum spanning trees, Discr. Appl. Math.157 (2009) 960. · Zbl 1169.05315 |
| [26] | Pettie, S. and Ramachandran, V., An optimal minimum spanning tree algorithm, J. ACM (JACM)49 (2002) 16. · Zbl 1323.05124 |
| [27] | Edmonds, J., Matroids and the greedy algorithm, Math. Programm.1 (1971) 127. · Zbl 0253.90027 |
| [28] | Karaganis, J. J., On the cube of a graph, Canad. Math. Bull11 (1968) 295. · Zbl 0162.27701 |
| [29] | P. J. Andersen and C. J. Ras, Algorithms for Euclidean degree bounded spanning tree problems, arXiv preprint arXiv:1809.09348. · Zbl 1430.68353 |
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.
