How to compute a minimum bottleneck spanning tree in linear time?

Question

We can find a minimum bottleneck spanning tree in O(E log*V) in the worst case by using Kruskal's algorithm. This is because every minimum spanning tree is a minimum bottleneck spanning tree.

But I got stuck on this job-interview question from this course.

How can we find a minimum bottleneck spanning tree in linear time even in the worst case. Note that we can assume that we can compute the median of n keys in linear time in the worst case.

Answer 1

1. Get V, the median of the weights of the |E| edges.
2. Find all edge's value no more than V, and get the subgraph
   • If the subgraph is connected, V is the upper limit of the answer, and decrease the V, repeat the step 1, 2.
   • If the subgraph is not connected, let the connected component to become a node, and increase the V, repeat the step 1, 2.

Then you can solve the question in linear time.

PS: Using DFS to judge the subgraph is connected. and the complexity is O(E/2) + O(E/4) + O(E/8) + ... = O(E)