PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Bertossi A. A., Pinotti M. C. Approximate L(delta(1), delta(2),..., delta(t))-coloring of trees and interval graphs. In: Networks, vol. 49 (3) pp. 204 - 216. Wiley, 2007.
 
 
Abstract
(English)
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.
Subject Channel Assignement
Wireless Network
C.2.1 Network Architecture and Design
G.2.2 Graph Theory


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional