4. (15 pts) We have a set of n transmitters and a set of available frequencies,

Question

4. (15 pts) We have a set of n transmitters and a set of available frequencies, la beled 1,2,...,m). Each transmitteri is assigned a subset of frequencies F C 11,2,. .,m), and it can only transmit on a frequency in Fi. (Different transmit- ters have different assigned sets.) In addition, there is a set of interfering transmitter pairs, which cannot transmit at the same frequency because they interfere. For instance, if (i, j) is an interfering pair with F 1,5,8 and F 2,5, 12,203, then i and j both cannot be allocated frequency 5. A frequency allocation is valid if each transmitter i gets a frequency from its assigned set Fand no two interfering transmitters get the same frequency. Prove that the frequency allocation problem is N P-complete.

Explanation / Answer

(a)-Formulate the frequency allocation problem as a graph problem. Let the vertices correspond to transmitters and edges correspond to interference between transmitters. Every vertex is labeled with a frequency range Fi . The question is whether one can allocate to each vertex a frequency from its frequency range so that no vertices are connected with an edge having the same frequency

(b)-Show that the frequency allocation problem is in NP. Guess (non-deterministic) a frequency assignment. Go through each vertex and verify that its frequency is in the frequency set. Go also through each edge and verify that the endpoint of the frequencies are different. This takes linear time in the size of the graph.

(c)-Show that the frequency allocation problem is NP-hard. Reduce k-coloring problem to frequency allocation: k-coloring(G, k) =

for each vertex vi in the graph G

Fi ? {1, . . . , k}

return FrequencyAllocation(G, {Fi})

Now, show that there is a k-coloring of graph Gi, there is a correct assignment of frequencies to G, where every vertex has frequency set {1, . . . , k}.

Suppose we have a k-coloring of G. Number the colors from 1 to k. If a vertex has color i, we assign to the corresponding vertex (transmitter) in the frequency allocation problem the frequency i. This is a correct frequency assignment because we have been based on a correct k-coloring.

In the other direction: assume that we have a correct frequency allocation. We get a kcoloring by allowing a vertex to have color i if the corresponding transmitter have been assigned frequency i.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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