Approximate L(?1, ?2, . . . , ?t)-Coloring of Trees and Interval Graphs

Given a vector (?1 , ?2 , . . . , ?t ) of nonincreasing positive integers, and an undirected graph G = (V , E ), an L(?1 , ?2 , . . . , ?t )-coloring of G is a function f from the ver- tex set V to a set of nonnegative integers such that |f (u ) - f (v )| >= ?i , if d (u , v ) = i , 1 <= i <= t , where d (u , v ) is the distance (i.e., the minimum number of edges) between the vertices u and v . An optimal L(?1 , ?2 , . . . , ?t )- coloring for G is one minimizing the largest integer used over all such colorings. Such a coloring problem has rele- vant applications in channel assignment for interference avoidance in wireless networks. This article presents efficient approximation algorithms for L(?1 , ?2 , . . . , ?t )- coloring of two relevant classes of graphs--trees, and interval graphs. Specifically, based on the notion of strongly simplicial vertices, O (n(t +?1 )) and O (nt 2 ?1 ) time algorithms are proposed to find ?-approximate colorings on interval graphs and trees, respectively, where n is the number of vertices and ? is a constant depending on t and ?1 , . . . , ?t . Moreover, an O (n) time algorithm is given for the L(?1 , ?2 )-coloring of unit interval graphs, which provides a 3-approximation. Specifically, based on the notion of strongly simplicial vertices, O (n(t +&#948;1 )) and O (nt 2 &#948;1 ) time algorithms are proposed to find &#945;-approximate colorings on interval graphs and trees, respectively, where n is the number of vertices and &#945; is a constant depending on t and &#948;1 , . . . , &#948;t . Moreover, an O (n) time algorithm is given for the L(&#948;1 , &#948;2 )-coloring of unit interval graphs, which provides a 3-approximation. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 204-216 2007