1 1 Minimum Bottleneck Spanning Trees 1.1 Minimum Bottleneck Spanning Trees

Let G = (V, E) be an undirected connected graph with a cost function w mapping edges to positive real numbers. A spanning tree is a tree connecting all vertices of G. The bottleneck edge of a spanning tree is the edge with the highest cost among all edges of that tree, there might be more than one bottleneck edge in a spanning tree in which they all have the same cost. A spanning tree T is called a minimum bottleneck spanning tree (MBST) if its bottleneck edge cost is minimum among all possible spanning trees. It is easy to see that a graph may have many MBSTs ( e.g. consider a graph where all edges ’ costs are the same, then all the spanning trees of that graph have same bottleneck edge cost and ̸ ∃ spanning tree with a bottleneck edge cost lower than any other spanning tree, therefore any spanning tree of such graph is a MBST. The well known problem Minimum Spanning Tree (MST) is related to MBST in which the Former is necessary an MBST while the opposite is not true. Therefore any algorithm that get an MST is also an algorithm to get an MBST. However we will see in the upcoming section an algorithm to get an MBST in O(E) time com