For a graph $G$ find the minimal $t$ such $G(t)=(V,E(t))$ is connected

Given a connected and directed graph $G=(V,E)$ with positive weights on the edges. for every $t>0$ we define $E(t)$ to be the group of edges with weight lower or equal than $t$. I need to find an efficient algorithm which computes the minimal $t$ such that $G(t)=(V,E(t))$ is connected.

I can sort all the edges with $|E|\log|E|$ complexity and try to take edges out of the graph from the heaviest to the easiet one, and to check with DFS if it is still connected, but its not effiecnt enough,

Any suggestions?

• Compute a minimum bottleneck spanning tree of the graph. (Actually just compute a minimum spanning tree, as a minimum spanning tree is a minimum bottleneck tree.)

• Determine the maximum edge weight from MBST, this will be your $t$.

• Remove all edges whose weight is higher.

This can be done in linear time in the sum of the number of nodes and edges (see wiki).

StackExchange Computer Science Q#3347, answer score: 8