Optimal Grid L(2,1_k) colorings

I was introduced to the Frequency AssignmentProblem (FAP) that arises in Wireless networks, by Prof Anil Shende.

It is an NP-complete problem, with the objective of finding an efficient frequency assignment scheme to a network of transmitters and receivers (together referred to as base-stations or simply stations), with the constraint that there should be no interference between signals emitted by any two (usually closely spaced) stations.
In our work, we model the wireless network as a graph where vertices represent the base-stations. Edges are drawn between vertices whose base-stations' transmissions can interfere. The frequency requirement of these stations is converted to a coloring on the nodes of the graph. The problem reduces to finding an optimal coloring scheme for the corresponding graph.

The minimum frequency-distance at which a frequency can be reused again is called the reuse distance s. A minimum channel separation of d_i is required between channels assigned to stations at distance i. Any coloring satisfying the above constraints is referred to as an L(d₁, d₂,...,d_s-1)-coloring . We introduced the notion of L(2,1_k)-colorings and obtained optimal L(2,1_k)-coloring schemes for bi-dimensional grids.

• FAP Web - A website about Frequency assignment. This is a comprehensive website, detailing the history of the problem. It also has a detailed bibliography, and is constantly updated.