Suppose you are designing a network of tree topology to connect n cities. For each pair of cities, say, ci and cj, the profit to build a fiber cable connecting ci and cj is given. Describe how to build a tree with fiber cables connecting these n cities with the maximum profit. What is the run-time complexity?

Lets try to solve this considering this algorithm:

Maximum_Profit (G = (V, E))

1. For each edge (u, v) in set E:-

2 ... Replace w (u, v) = - w (u, v) / /replace the weight of each edge by its negative value

3. Tree T = Minimum_Spanning_Tree (G = (V, E))

4. Tree T is the desired Maximum Spanning Tree which will maximize our profit.

This algorithm will take O ((E+V) log V) which is the time taken by Prim's algorithm to compute Minimum spanning tree.

Explaining the algorithm below;

We can represent the network in the form of undirected weighted graph G = (V, E) such that each vertex represent different cities and the weight of each edge represent the profit associated with that fiber cable.

Now in order to maximize the profit, we will create maximum spanning tree. Just like minimum spanning tree of a graph G = (V, E) is a spanning tree with minimum total weight, we will create a maximum spanning tree which will connect n cities with n-1 links with maximum possible profit.

In order to obtain a Maximum spanning tree, we simply will have to replace weight of each edge by its negative value and then perform algorithm for finding Minimum Spanning Tree like Prim's algorithm.

The next on line of things to do is to replace these negative weights by positive value on the minimum spanning tree, we will get Maximum Spanning tree which is our desired result.

Therefore, referencing our algorithm again, This algorithm will take O ((E+V) log V) which is the time taken by Prim's algorithm to compute Minimum spanning tree.