Linear deterministic algorithm for finding spanning tree T with minimal maximum edge

Question

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.

Answer 1

As it looks like a homework problem, I will not give you a complete solution rather than a hint.

We need to find such $W$ that the graph with edges of weight $\leq W$ is connected. Consider an edge with median weight $M$, like you do in the binary search.

• What if the graph with all edges with weight $\leq M$ is connected? Can we discard some edges completely and reduce the problem to the one where the graph has twice as less edges?
• What if the graph will all edges with weight $\leq M$ is not connected? Can we take some edges unconditionally now, process the graph somehow and reduce the probem to the one where the graph has twice as less edges?