Approximate L(?1, ?2, . . . , ?t)-Coloring of Trees and Interval Graphs
Bertossi A. A., Pinotti M. C.
Channel Assignement Wireless Network
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 +δ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. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 204-216 2007
Source: Networks (N.Y.N.Y., Print) 49 (2007): 204–216.
Publisher: Wiley, New York , Stati Uniti d'America
Back to previous page
@article{oai:it.cnr:prodotti:43969,
title = {Approximate L(?1, ?2, . . . , ?t)-Coloring of Trees and Interval Graphs},
author = {Bertossi A. A. and Pinotti M. C.},
publisher = {Wiley, New York , Stati Uniti d'America},
journal = {Networks (N.Y.N.Y., Print)},
volume = {49},
pages = {204–216},
year = {2007}
}
0000-0002-1015-7031