Channel Assignment on Strongly-Simplicial Graphs

Given a vector ( d_1, d_2, d_3, ..., d_t ) of non increasing positive integers, and an undirected graph G = (V,E), an L ( d_1, d_2, d_3, ..., d_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) | >= i, if d(u , v) = i, for each i = 1,2, ..., t, where d(u , v) is the distance (i.e. the minimum number of edges) between the vertices u and v. This paper presents e cient algorithms for nding optimal L(1, ..., 1)-colorings of trees and interval graphs. Moreover, e cient algorithms are also provided for nding approximate L (1, ..., 1)-colorings of trees and interval graphs, as well as approximate L ( 1, 2)-colorings of unit interval graphs.