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 |

1) Download Document PDF |

Open access Restricted Private