A group of network designers at the communications company CluNet find themselves facing the following problem....

 

Transcribed Image Text:

A group of network designers at the communications company CluNet find themselves facing the following problem. They have a connected graph G = (V. E), in which the nodes represent sites that want to communicate. Each edge e is a communication link, 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 will communicate. 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 the maximum, 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 the network designers makes a bold suggestion: Maybe one can find a spanning tree T of G so that for every pair of nodes u, v, the unique u-v path in the tree actually attains the best achievable bottleneck rate for u, v in G. (In other words, even if you could choose any u-v path in the whole graph, you couldn't do better 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 for the skepticism: each pair of nodes might want a very different-looking path to maximize its bottleneck rate; why should there be a single tree that simultaneously makes everybody happy? But after some failed 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, give an algorithm constructing a spanning tree T in which, for each u, v & V. the bottleneck rate of the u-v path in T is equal to the best achievable bottleneck rate for the pair u, v in G. A group of network designers at the communications company CluNet find themselves facing the following problem. They have a connected graph G = (V. E), in which the nodes represent sites that want to communicate. Each edge e is a communication link, 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 will communicate. 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 the maximum, 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 the network designers makes a bold suggestion: Maybe one can find a spanning tree T of G so that for every pair of nodes u, v, the unique u-v path in the tree actually attains the best achievable bottleneck rate for u, v in G. (In other words, even if you could choose any u-v path in the whole graph, you couldn't do better 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 for the skepticism: each pair of nodes might want a very different-looking path to maximize its bottleneck rate; why should there be a single tree that simultaneously makes everybody happy? But after some failed 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, give an algorithm constructing a spanning tree T in which, for each u, v & V. the bottleneck rate of the u-v path in T is equal to the best achievable bottleneck rate for the pair u, v in G.

Answer rating: 100% (QA)

Show that such a tree exists and give an efficient a... View the full answer