Journal article

Algorithms for Euclidean Degree Bounded Spanning Tree Problems

PJ Andersen, CJ Ras

International Journal of Computational Geometry & Applications | Published : 2019


Given a set of points in the Euclidean plane, the Euclidean d-minimum spanning tree (d-MST) problem is the problem of finding a spanning tree with maximum degree no more than d for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean d-minimum bottleneck spanning tree (d-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 d ≤ 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 approximat..

View full abstract

Citation metrics