page_title: Minimum bottleneck spanning tree
section_title: Example
hierarchical_section_title: Minimum bottleneck spanning tree / MBSA algorithms for directed graphs / Gabow and Tarjan algorithm for MBSA / Example
caption_attribution_description: English: MBSA-GT example 2
context_page_description: In mathematics, a minimum bottleneck spanning tree in an undirected graph is a spanning tree in which the most expensive edge is as cheap as possible. A bottleneck edge is the highest weighted edge in a spanning tree. A spanning tree is a minimum bottleneck spanning tree if the graph does not contain a spanning tree with a smaller bottleneck edge weight. For a directed graph, a similar problem is known as Minimum Bottleneck Spanning Arborescence.
context_section_description: The following example shows that how the algorithm works.
  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 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 ≤ λ*.
caption: 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.
exif: {}