A group of network designers at the communicationscompany CluNet find themselves facing the following problem. They have a connected undirected graphG = (V, E), in which the nodes represent sites that want to communicate. Each edge e is a communicationlink, with a given available bandwidth be.
For each pair of nodes u, v ? V , they want to select a single u-v path P on which this pair willcommunicate. The bottleneck rate b(P) of this path P is the minimum bandwidth of any edge it contains;that is, b(P) = mine?P be. The best achievable bottleneck rate for the pair u, v in G is simply themaximum, over all u-v paths P in G, of the value b(P).
It?s getting to be very complicated to keep track of a path for each pair of nodes, and so one of thenetwork designers makes a bold suggestion: May be one can find a spanning tree T of G so that for everypair of nodes u, v, the unique u-v path in the tree actually attains the best achievable bottleneck rate foru, v in G. (In other words, even if you could choose any u-v path in the whole graph, you couldn?t dobetter than the u-v path in T.)
This idea is roundly heckled in the offices of CluNet for a few days, and there?s a natural reason forthe skepticism: each pair of nodes might want a very different-looking path to maximize its bottleneckrate; why should there be a single tree that simultaneously makes everybody happy? But after somefailed attempts to rule out the idea, people begin to suspect it could be possible.
Show that such a tree exists, and give an efficient algorithm to find one. That is, given an algorithmconstructing a spanning tree T in which, for each u, v ? V , the bottleneck rate of the u-v path in T equalto the best achievable bottleneck rate for the pair u, v in G. (page 198, algorithm design by jon kleinberg, eva tardos)