Channel assignment on strongly-simplicial graphs

Given a vector ( 1; 2; : : : ; t) of non increasing pos- itive integers, and an undirected graph G = (V;E), an L( 1; 2; : : : ; t)-coloring of G is a function f from the vertex set V to a set of nonnegative integers such that jf(u) -- f(v)j i, if d(u; v) = i; 1 i t; where d(u; v) is the distance (i.e. the minimum num- ber of edges) between the vertices u and v. This paper presents e cient algorithms for nding opti- mal L(1; : : : ; 1)-colorings of trees and interval graphs. Moreover, e cient algorithms are also provided for nding approximate L( 1; 1; : : : ; 1)-colorings of trees and interval graphs, as well as approximate L( 1; 2)- colorings of unit interval graphs