Channel Assignment with Separation on Trees and Interval Graphs

Given a vector $(\delta_1, \delta_2, \ldots, \delta_{t})$ of non increasing positive integers, and an undirected graph $G=(V,E)$, an $L(\delta_1, \delta_2, \ldots,\delta_{t})$-coloring of $G$ is a function $f$ from the vertex set $V$ to a set of nonnegative integers such that $|f(u)-f(v)| \ge \delta_i$, if $d(u,v) = i, \ 1 \le i \le t, \ $ where $d(u,v)$ is the distance (i.e. the minimum number of edges) between the vertices $u$ and $v$. An optimal $L(\delta_1, \delta_2, \ldots,\delta_{t})$-coloring for $G$ is one minimizing the largest used integer over all such colorings. This coloring problem has relevant application in channel assignment for interference avoidance in wireless networks, where channels (i.e. colors) assigned to interfering stations (i.e. vertices) at distance $i$ must be at least $\delta_i$ apart, while the same channel can be reused only at stations whose distance is larger than $t$. This paper presents efficient algorithms for finding optimal $L(1, \ldots, 1)$-colorings of trees and interval graphs as well as optimal $L(2,1,1)$-colorings of complete binary trees. Moreover, efficient algorithms are also provided for finding approximate $L(\delta_1,1, \ldots, 1)$-colorings of trees and interval graphs as well as approximate $L(\delta_1,\delta_2)$-colorings of unit interval graphs.