Assegnamento di canali in reti wireless.

In [A9], è studiato il problema di allocare risorse per la comunicazioni (per esempio, canali di frequenze e time-slots) alle stazioni base delle reti senza fili (WLAN, Wireless Local Loop, reti cellulari) in modo tale che stazioni vicine usino frequenze molto diverse per evitare interferenze nelle trasmissioni, le stesse frequenze siano riutilizzate solo a distanza superiore di una soglia prestabilita e il numero di frequenze usate sia minimo. In particolare, sono considerate due versioni molto realistiche del problema di assegnamento, equivalenti a varianti di problemi di colorazione di grafi, dove le frequenze sono rappresentate con numeri interi. La differenza fra le frequenze assegnate a due stazioni adiacenti deve essere di almeno 2, mentre la stessa frequenza può essere riutilizzata in stazioni a distanza almeno 3 o 4. Essendo il problema $NP$-hard, sono state proposte soluzioni ottime per famiglie speciali di grafi, quali anelli, alberi, reti esagonali e reti cellulari. In questi casi particolari, la frequenza assegnabile a ciascuna stazione si calcola in tempo costante o al piú logaritmico. Inoltre, in [C3], osservato che il problema dell'interferenze sarà sempre più esteso dato l'uso di una rete sempre più capillare, si è generalizzato il problema di assegnamento come segue. Modellata la rete con un grafo, e dati la distanza di riuso $s$ ed un vettore di separazione $[d(1), d(2), ... , d(s-1)]$, il problema consiste nell'assegnare ad ogni nodo $x$ del grafo un colore $f(x)$ tale che lo scarto tra $f(y)$ ed $f(x)$ non scenda sotto $d(i)$ ogniqualvolta la distanza (numero minimo di archi) tra le stazioni $x$ ed $y$ è uguale a $i$ ed il massimo colore usato è minimizzato. Per reti regolari sono progettati algoritmi ottimi o approssimati di complessità polinomiale sia per distanza di riuso $s=4$ e per vettori di separazione $[1,1,1]$ e $[2,1,1]$ che per distanza di riuso arbitraria $s$ e vettori di separazione $[2,1, \dots, 1]$. Per le reti ad albero, a grafo di intervalli e a griglia esagonale (Honeycomb grid), in [C6] e in [C7], sono stati progettati algoritmi ottimi o approssimati di complessità polinomiale per vettori di separazione $[1,1,\ldots,1]$ e $[\delta_1, \delta_2]$.