Minimum bottleneck spanning trees with degree bounds. Issue 4 (30th September 2016) - Andersen, Patrick J.; Ras, Charl J.
Abstract : Given a graph G with edge lengths, the minimum bottleneck spanning tree (MBST) problem is to find a spanning tree where the length of the longest edge in tree is minimum. It is a well‐known fact that every minimum spanning tree (MST) is a minimum bottleneck spanning tree. In this article, we introduce the δ ‐MBST problem, which is the problem of finding an MBST such that every vertex in the tree has degree at most δ . We show that optimal solutions to the similarly defined δ ‐MST problem are not necessarily optimal solutions to the δ ‐MBST, and we establish that the δ ‐MBST problem is NP‐complete for any δ ≥ 2 . We show that when edge lengths of the graph are Euclidean distances between points in the plane, the problem is NP‐hard for δ = 2 and 3, and tractable for δ ≥ 5 . We give a dual approximation scheme for the general graph version of the problem which is the best possible with respect to feasibility. For the Euclidean version, we give a 3 ‐factor approximation algorithm for the 4‐MBST. We also give a 2‐factor algorithm for the Euclidean 3‐MBST and a 3‐factor approximation algorithm for the general Euclidean δ ‐MBST, both of which can be generalized to metric spaces. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(4), 302–314 2016