New answers tagged weighted-graphs
0
The important part is that you start with an MST for the original graph. With this extra piece of information, you can build a proof by contradiction, as follows:
Construct the new tree as described (add the edge, check the cycle, remove the edge with the largest weight), now assume for contradiction that this tree is not an MST. This may be for several ...
1
We can solve the problem in $\mathcal{O}(E \log V)$ by binary search.
We can identify the strongly connected components in a graph in linear ($\mathcal{O}(V + E)$) time. Thus we can check if the graph is strongly connected in linear time.
If $G(t_{0}) = (V, E(t_{0}))$ is strongly connected, so is $G(t) = (V, E(t))$ for $t \geq t_{0}$. Further, if $G(t_{0})$...
Top 50 recent answers are included
