Frequency Assignment

Problem

A mobile radio network assigns frequencies to its clients. If two clients are sufficiently close to each other, they must be assigned different frequencies. If they are far enough from each other they may share the frequency. Your task is to create an assignment that minimizes the amount of frequencies used (optimization problem) or an assignment where the amount of frequencies used is at most a given bound K (decision problem).

Input

A graph with each node representing a mobile radio client and for the decision problem K, the number of frequencies allowed. An edge means that the clients represented by the endpoints are too close to each other to use same frequency.

Output

Local Search

Assignments for integer variables n1,n2..
ni = f; means that node ni uses frequency f, where f is a nonnegative integer.
Example output:

n1 = 0;
n2 = 2;
n3 = 3;

Linear Program

Assignments for integer variables n1,n2..
ni = f means that node ni uses frequency f, where f is a nonnegative integer.

SAT

Assignments for boolean variables nifj, j=0..K-1
nifj = 1, if node ni is using frequency j
nifj = 0, otherwise

Example instances

Instance with 3 frequencies
Instance with 12 frequencies
Instance with 15 frequencies