Minimum bottleneck spanning tree

Minimal Bottleneck Spanning Tree ${\displaystyle G(V,E)}$

In an undirected graph G(V, E) and a function w : E → R, let S be the set of all spanning trees T_i. Let B(T_i) be the maximum weight edge for any spanning tree T_i. We define subset of minimum bottleneck spanning trees S′ such that for every T_j ∈ S′ and T_k ∈ S we have B(T_j) ≤ B(T_k) 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).

Minimal Bottleneck Spanning Arborescence G(V,E)

An arborescence of graph G is a directed tree of G which contains a directed path from a specified node L to each node of a subset V′ of V \{L}. Node L is called the root of arborescence. An arborescence is a spanning arborescence if V′ = V \{L}. MBST in this case is a spanning arborescence with the minimum bottleneck edge. An MBST in this case is called a Minimum Bottleneck Spanning Arborescence (MBSA).

The graph on the right is an example of MBSA, the red edges in the graph form a MBSA of G(V, E).

The procedure has two input parameters. G is a graph, w is a weights array of all edges in the graph G.[6]

 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) ${\displaystyle \cup }$ F

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

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 forest in O(E)
• considering half edges in E in each iteration O(E + E/2 + E/4 + ··· + 1) = O(E)

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 edges 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 edges 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 edges set. A forest formed within each disconnected component will be part of a MBST in the original graph.
	Repeat similar steps by combining more vertices into a super vertex.
	The algorithm finally obtains a MBST by using edges it found during the algorithm.

For a directed graph, Camerini's algorithm focuses on finding the set of edges that would have its maximum cost as the bottleneck cost of the MBSA. This is done by partitioning the set of edges E into two sets A and B and maintaining the set T that is the set in which it is known that G_T does not have a spanning arborescence, increasing T by B whenever the maximal arborescence of G(B ∪ T) is not a spanning arborescence of G, otherwise we decrease E by A. The total time complexity is O(E log E).[5][4]

function MBSA(G, w, T) is
    E ← the set of edges of G 
    if | E − T | > 1 then
        A ← UH(E-T)
        B ← (E − T) − A
        F ← BUSH(GBUT)
        if F is a spanning arborescence of G then
            S ← F
            MBSA((GBUT), w, T)
        else
            MBSA(G, w, TUB);

1. T represents a subset of E for which it is known that G_T does not contain any spanning arborescence rooted at node “a”. Initially T is empty
2. UH takes (E−T) set of edges in G and returns A ⊂ (E−T) such that:
   1. ${\displaystyle |A|=\left\lfloor {\frac {(|E-T|)}{2}}\right\rfloor }$
   2. W_a ≥ W_b , for a ∈ A and b ∈ B
3. BUSH(G) returns a maximal arborescence of G rooted at node “a”
4. The final result will be S

Gabow and Tarjan provided a modification of Dijkstra's algorithm for single-source shortest path that produces an MBSA. Their algorithm runs in O(E + V log V) time if Fibonacci heap used.[7]

 For a graph G(V,E), F is a collection of vertices in V. 
 Initially, F = {s} where s is the starting point of the graph G and c(s) = -∞

 1  function MBSA-GT(G, w, T)
 2      repeat |V| times
 3          Select v with minimum c(v) from F; 
 4          Delete it from the F;
 5          for ∀ edge(v, w) do
 6              if w ∉ F or ∉ Tree then
 7                  add w to F;          
 8                  c(w) = c(v,w);
 9                  p(w) = v;     
 10             else
 11                 if w ∈ F and c(w) > c(v, w) then
 12                     c(w) = c(v, w);
 13                     p(w) = v;

The following example shows that how the algorithm works.

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.

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. K(i) = 2^k(i − 1) with k(1) = 2. The algorithm finds λ^* in which it is the value of the bottleneck edge in any MBSA. After λ^* is found any spanning arborescence in G(λ^*) is an MBSA in which G(λ^*) is the graph where all its edge's costs are ≤ λ^*.[4][7]