Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ).
I need to find a linear deterministic algorithm of finding a spanning tree T with minimum maximum edge e. We were given a hint of using binary search.
I already proved that for MST of G, $λ$(MST) <= $λ$(T) for every T spanning tree of G.
The problem that using Prim or Kruskal algorithm is not linear, and I'm trying to find a special property for such tree.
I already tried:
(In assumption I get the edges sorted): use binary search with the next comparator: remove all edges with weight above current weight. use BFS. If the graph is connected, "move left" (possible connected graph with a lighter edge) else, "move right" (can't connect the graph with only the edges that are in weight of the current weight and lighter).
the problem is that it is O(ElogE) because we need logE iterations for the binary search and E for BFS each time.