CMI2010-B-01a

Question

An international cellphone company provides service on $7$ different frequencies. They wish to set up business in TamilNadu and have fixed the locations of $100$ towers for their new service. The company has to ensure that two towers broadcasting on the same frequency are at least $100$ km apart, so that there is no interference of signals.

Model this problems using graphs.

Answer 1

The solution is given below. 

Comments

ok....thankyou

---

How about we model it this way:

For all pair of nodes(towers) an edge connects them only if they are more than a 100 Km apart. Then we find the number of connected components ( C ) in the graph, if C <= 7, it is feasible else not. This way we'll be able to do it in polynomial time as C can be calculated using BFS or DFS in O(v+e) time complexity. 

Can anyone help me figure out if I'm wrong with this solution somewhere?

I agree with @Kushagra's solution it's just that for this problem v = 100 and hence we would not be able to comment on the feasibility using the k-colorable algorithm.

---

Consider this problem where there are three towers $T_1$,$T_2$,$T_3$ and there are three frequencies $F_1$,$F_2$,$F_3$. The distance between $T_1$ and $T_2$ is 50kms. and the distances between ($T_1$,$T_3$) and ($T_2$,$T_3$) be greater than 100kms.

Now, suppose you are required to find whether is it possible to provide services to all the three frequencies with the above three towers.

Will your solution work in this case?

To find the chromatic number of a graph is NP-complete. But there exists many polynomial time approximation algorithms to find the chromatic number of a graph which outputs the chromatic number of a graph with some error. So, we can use one of those algorithms and try to improve on the solution given by algorithm. This might take exponential time but theoritically we can comment about the feasibility.

One example of the approximation algorithm for k-colourabality problem is given in the following link

https://www.youtube.com/watch?v=h9wxtqoa1jY&list=PLB7540DEDD482705B&index=6