NASA wants to link N stations spread over the country using communication channe

Question

NASA wants to link N stations spread over the country using communication channels. For every pair of stations, there is a badnwidth associated with the channel between them, which is known a priori. It (NASA) wants to select N ? 1 channels (the minimum possible) in such a way that all the stations are linked by the channels and the total bandwidth (defined as the sum of the individual bandwidths of the channels) is maximum. Give an efficient algorithm for this problem and determine its worst-case time complexity.

Explanation / Answer

Let us try to understand the problem properly, we have the following observations:

a) NASA has N stations across the country

b) Sations are connected via channels

c) Each channel has different bandwidth

d) We need to connect all the N stations with maxiimizing the sum of channels connecting.

Now, let us model the above problem to a standard problem, let us see how to do it

1) Consider every station as the node of a graph

2) Consider every channel as the edge of graph conecting nodes

3) Consider the bandwith of the channel as the weight of the graph

What we need to do is find out the maximum weight subgraph that connects all the vertices or In a beter way we can say that we need to find out the maximum spanning tree in the graph

Now, our problem has been modeled to a standard Maximum spanning tree problem

There are many popular algorithm to solve the Minimum spanning tree problem like prim's algorithm, kruskal's algorithm which can be modified to get maximum spanning tree..

We will be using modified Kruskal's algorithm.

Here is our algorithm for given problem:

1) Sort the channels according the bandwidth in descending order

2) Start adding channels to a new graph starting from the channel with highest bandwidth

3) If adding a channel creates a cycle in the new graph, skip the channel

Complexity analysis

To sort the channels in the descending order, channels are associated with every pair stations, so, no of cahnnels are of the order O(N2) . So, it will take N2log N2 or 2N2logN or O(N2logN)

To check the cycle in the graph, we can applyDFS which will run in O(N2) time

Total time complexity = O(N2logN)

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.