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

The standard algorithm for finding Minimum Bottleneck Spanning Tree (MBST) is known as Camerini’s algorithm. It runs in linear time and is as follows:

 1. Find a median edge weight in graph and partition all edges in to two
    partitions A and B around it. Let A have all edges greater than
    pivot and B has all edges less than or equal to pivot.                
 2. Run DFS or BFS on partition B. If it connected graph then again run
    step 1 on it.        
 3. If partition B wasn't a connected graph then we must have more than
    1 connected components in it. Create a new graph by contracting each
    of these connected components as a single vertex and select edges
    from partition A that connects these components. MBST is given by
    edges in connected components + MBST of new graph.

In pseudo-code:

1:  procedure MBST(V, E)
2:      if |E| = 1 then
3:          Return E 
4:      else
5:          A, B ←  Partition E in two halves around median
6:                  A is higher half, B is lower half
7:          F ← Connected components of B
8:          if |F| = 1 and spans all vertices then
9:              Return MBST(V, B)
10:         else
11:             V' ← create one vertex for each connected component in F
12:                     plus vertices missing from F
13:             B' ← Edges from A that connects components in F
14:                     and edges to vertices not in F
15:             Return F ∪ MBST(V', B') 
16:         end if
17:     end if
18: end procedure

Implementation notes:

1. Median can be found in O(n).
2. Line 7 can generate disjoint-set data structure using BFS or DFS.
3. Line 13 involves filtering out edges in A where each edge has endpoints that are either in two different connected components in F or one endpoint is vertex not in F and other is in F or both are not in F. This tests can be done using efficient disjoint-set data structure in O(1) amortized time for each edge.

Update: I've now also created Wikipedia page on this topic.