Minimum bottleneck spanning tree

[1] For a directed graph, a similar problem is known as Minimum Bottleneck Spanning Arborescence (MBSA).

We define subset of minimum bottleneck spanning trees S′ such that for every Tj ∈ S′ and Tk ∈ S we have B(Tj) ≤ B(Tk) for all i and k.[2] The graph on the right is an example of MBST, the red edges in the graph form a MBST of G(V, E).

An MBST in this case is called a Minimum Bottleneck Spanning Arborescence (MBSA).

[3] [4] Camerini proposed[5] an algorithm used to obtain a minimum bottleneck spanning tree (MBST) in a given undirected, connected, edge-weighted graph in 1978.

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.

[5][4] Gabow and Tarjan provided a modification of Dijkstra's algorithm for single-source shortest path that produces an MBSA.

Another approach proposed by Tarjan and Gabow with bound of O(E log* V) for sparse graphs, in which it is very similar to Camerini’s algorithm for MBSA, but rather than partitioning the set of edges into two sets per each iteration, K(i) was introduced in which i is the number of splits that has taken place or in other words the iteration number, and K(i) is an increasing function that denotes the number of partitioned sets that one should have per iteration.

Minimal Bottleneck Spanning Tree ⁠ ⁠
Minimal Bottleneck Spanning Arborescence G(V,E)
At the first step of the algorithm, we select the root s from the graph G, in the above figure, vertex 6 is the root s. Then we found all the edge(6,w) ∈ E and their cost c(6,w), where w ∈ V.
Next we move to the vertex 5 in the graph G, we found all the edge(5,w) ∈ E and their cost c(5,w), where w ∈ V.
Next we move to the vertex 4 in the graph G, we found all the edge(4,w) ∈ E and their cost c(4,w), where w ∈ V. We find that the edge(4,5) > edge(6.5), so we keep edge(6,5) and remove the edge(4,5).
Next we move to the vertex 1 in the graph G, we found all the edge(1,w) ∈ E and their cost c(1,w), where w ∈ V. We find that the edge(5,2) > edge(1,2), so we remove edge(5,2) and keep the edge(1,2).
Next we move to the vertex 2 in the graph G, we found all the edge(2,w) ∈ E and their cost c(2,w), where w ∈ V.
Next we move to the vertex 3 in the graph G, we found all the edge(3,w) ∈ E and their cost c(3,w), where w ∈ V. We find that the edge(3,4) > edge(6,4), so we remove the edge(3,4) and keep the edge(6,4).
After we loop through all the vertices in the graph G, the algorithm has finished.