1. Algorithms for Euclidean Degree Bounded Spanning Tree Problems.
- Author
-
Andersen, Patrick J. and Ras, Charl J.
- Subjects
- *
EUCLIDEAN algorithm , *SPANNING trees , *HEURISTIC algorithms , *APPROXIMATION algorithms , *POINT set theory , *DISCRETE geometry - Abstract
Given a set of points in the Euclidean plane, the Euclidean δ -minimum spanning tree (δ -MST) problem is the problem of finding a spanning tree with maximum degree no more than δ for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean δ -minimum bottleneck spanning tree (δ -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 δ ≤ 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. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF