An improved algorithm for the constrained bottleneck spanning tree problem

The authors propose an algorithm to solve the bottleneck spanning tree problem with an additional linear constraint. The present algorithm has an improved worst case performance over the best known algorithm for this problem. In a graph with n nodes and m edges such that m≥O(nlognloglog*n), where log*n is the iterative logarithm of n, the present algorithm runs in O(m) time and hence is the best possible in that case. For a large class of graphs, the proposed algorithm has almost the same complexity as that of computing just one minimum spanning tree.