An Improved Algorithm for the Constrained Bottleneck Spanning Tree Problem

We propose an algorithm to solve the bottleneck spanning tree problem with an additional linear constraint. Our 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(n log n log log*n), where log* n is the iterative logarithm of n, our 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.