Minimum bottleneck spanning trees with degree bounds. Issue 4 (30th September 2016)

• Record Type: Journal Article
• Authors: Andersen, Patrick J.; Ras, Charl J.
• Is Part Of: Networks. Volume 68:Issue 4(2016)
• Page Start: 302
• Page End: 314
• Publication Date: 2016-09-30
• Subjects: minimum spanning trees -- bottleneck objective -- approximation algorithms -- discrete geometry -- bounded degree -- combinatorial optimization; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21710
• Languages: English
• ISSNs: 0028-3045

Abstract

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