snippetMinor
How to find spanning tree of a graph that minimizes the maximum edge weight?
Viewed 0 times
themaximumgraphhowweightedgethatfindminimizesspanning
Problem
Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am having a lot of trouble proving that my idea is actually correct. Can anyone show me a proof sketch or give me some hints as to how to construct the proof? Thanks!
Solution
What follows is taken from Tsuyoshi Ito's comment.
If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.)
If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.)
Context
StackExchange Computer Science Q#2226, answer score: 5
Revisions (0)
No revisions yet.