Minimum bottleneck spanning trees with degree bounds

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