Suppose you are a manager in the IT department for the government of a corrupt d
ID: 3815768 • Letter: S
Question
Suppose you are a manager in the IT department for the government of a corrupt dictator, who has a collection of computers that need to be connected together to create a communication network for his spies. You are given a weighted graph, G, such that each vertex in G is one of these computers and each edge in G is a pair of computers that could be connected with a communication line. It is your job to decide how to connect the computers. Suppose now that the CIA has approached you and is willing to pay you various amounts of money for you to choose some of these edges to belong to this network (presumably so that they can spy on the dictator). Thus, for you, the weight of each edge in G is the amount of money, in U.S. dollars, that the CIA will pay you for using that edge in the communication network.
Describe an efficient algorithm, therefore, for finding a maximum spanning tree in G, which would maximize the money you can get from the CIA for connecting the dictator’s computers in a spanning tree. What is the running time of your algorithm?
Explanation / Answer
This can be done using greedy algorithms...
It gives maximum spinning tree which maaximize the money...
Algorithm steps:
1) Firstly sort the available computers as per given weighted graph .. (descending order)
2) Then get the maximum edge and connect, but check condition that there should not be any cycles.
3) Repeat step2 until v-1 edges in the graph.
------------------------------------------------------------------------------------------------------------------------------------------------------------
It would maximize the money and computing the running time..
To insert edge it takes O(lg E)
remove edge will take O(lg V)
So finally running time will be O(E log V)