Minimum bottleneck spanning tree

Camerini proposed an algorithm used to obtain a minimum bottleneck spanning tree (MBST) in a given undirected, connected, edge-weighted graph in 1978. It half divides edges into two sets. The weights of edges in one set are no more than that in the other. If a spanning tree exists in subgraph composed solely with edges in smaller edges set, it then computes a MBST in the subgraph, a MBST of the subgraph is exactly a MBST of the original graph. If a spanning tree does not exist, it makes each disconnected component into a new super vertex, then computes a MBST in the graph formed by these super vertices and edges in the larger edges set. A minimum bottleneck forest in each disconnected component is part of a MBST in original graph. Repeat this process until two (super) vertices are left in the graph and a single edge with smallest weight between them is to be added. A MBST is found consisting of all the edges found in previous steps.

Pseudocode

 1  function MBST(graph G, weights w)
 2  E ← the set of edges of G 
 3  if | E | = 1 then return E else
 4     A ← half edges in E whose weights are no less than the median weight
 5     B ← E - A
 6     F ← forest of GB
 7     if F is a spanning tree then
 8        return MBST(GB,w)
 9     else
 10       return MBST((GA)η w)

In the above (G_A)_η is the subgraph composed of super vertices (by making vertices in a disconnected component as one) and edges in A.

Example

In the following example green edges are used to form a MBST and dashed red areas indicate super vertices formed during the algorithm steps.

	The algorithm half divides edges in two sets with respect to weights. Green edges are those edges whose weights are as small as possible.
	Since there is a spanning tree in the subgraph formed solely with edges in the smaller set. Repeat finding a MBST in this subgraph.
	Since there is not a spanning tree in current subgraph formed with edges in the current smaller set. Combine the vertices of a disconnected component to a super vertex (denoted by a dashed red area) and then find a MBST in the subgraph formed with super vertices and edges in larger set. A minimum bottleneck forest formed within each disconnected component will be part of the MBST in the original graph
	Repeat similar steps by combing more vertices into a super vertex.
	The algorithm finally obtains a MBST by using edges it founds during the algorithm.

Running time

The algorithm is running in O(E) time, where E is the number of edges. This bound is achieved as follows:

• dividing into two sets with median-finding algorithms in O(E)
• finding a minimum bottleneck forest in O(E)
• considering half edges in E in each iteration O(E + E/2 + E/4 + ··· + 1) = O(E)

References

• Camerini, P.M. (1978), "The min-max spanning tree problem and some extensions", Information Processing Letters, 7 (1).