CMI2010-B-01b

Question

An international cellphone company provides service on 7 different frequencies. They wish to set up business in Tamil Nadu 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.

1. Describe an algorithm which will answer the question “Is it feasible to set up towers at the given locations and provide service on 7 different frequencies?”. Your algorithm should say “feasible” if it is feasible, otherwise output the minimum number of frequencies needed to utilise all 100 towers.

Answer 1

https://gateoverflow.in/46130/cmi2010-b-01a

Answer 2

$\underline{\textbf{Facts:}}$

1. $N$ towers are installed over some area $A$

2. Company provides services of $k$ frequencies

3. $N\ge k$

$\underline{\textbf{Objective:}}$

To design an algorithm that outputs "feasible" when all the $k$ frequencies can be provided as service over all the $N$ towers, else the minimum number of frequencies needed to cover all the $N$ towers.

Under this scenario, particular problem will have a trivial solution of being "feasible" every time. Hence we are provided with certain constraints.

$\underline{\textbf{Constraints:}}$

Two towers broadcasting on same frequency are greater than equal to $R$ KM apart.

$\underline{\textbf{Design:}}$

We can use graphs to model this problem, where vertex would represent towers and edges between any two towers would indicate distance between them, forming an undirected simple complete graph on $N$ vertices. Lets' notate this graph as $G(V,E)$.

$\underline{\textbf{Preliminary Observations:}}$

$\forall_{u,v \ \in \ V} \ D(u,v)<R \implies f(u) \neq f(v)$, where $V$ is the set of vertices/towers, $D:V \times V \rightarrow \mathbb{R}$ is distance between two towers, $f:V \rightarrow [k]$ is frequency assignment function to any tower. $[k] = \{1,2,\dots,k\}$

$\forall_{u,v \ \in \ V} \ D(u,v)\ge R \implies [f(u) \neq f(v)]\lor [f(u) = f(v)]$. So frequency assignment doesn't have any constraints until and unless distance between them is greater than equal to $R$ KM.

$\underline{\textbf{Re-Design:}}$

Since frequency assignment is dependent on distances less than $R$ KM, then we can remove the edges with greater than equal to $R$ KM distance. Lets' notate this graph as $\overline{G}(V, \overline{E})$

$\underline{\textbf{Idea:}}$

Finding minimal number of frequency assignments over $N$ towers where no two connected towers have same frequency (definition of $\textbf{Graph Coloring}$) can tell us if its' feasible to provide services on $k$ frequencies or not.

When $\chi(\overline{G}) \le k$ then $\overline{G}$ is $k$-colorable too. Here, $\chi(\cdot)$ is chromatic number. However, $\overline{G}$ is not $k$-colorable if $\chi(\overline{G})>k$. Hence, finding chromatic number can get the job done.

$\underline{\textbf{Algorithm:}}$

$\underline{\text{Step 1}}:$ Design the data structure for graph $G$

$\underline{\text{Step 2}}:$ Remove edges with distance more than equal to $R$ KM and call this $\overline{G}$

Output = $\begin{cases}\text{feasible} & \chi(\overline{G}) \le k \\ \chi(\overline{G}) & \chi(\overline{G}) > k \end{cases}$