ApproximateL(δ1,δ2,…,δt)‐coloring of trees and interval graphs
Alan A. Bertossi, Cristina Maria Pinotti · Networks · 2007
Abstract Given a vector (δ1,δ2,…,δt) of nonincreasing positive integers, and an undirected graphG= (V,E), anL(δ1,δ2,…,δt)‐coloring ofGis a functionffrom the vertex setVto a set of nonnegative integers such that ∣f(u) −f(v)∣ ≥ δi, ifd(u,v) =i, 1 ≤i≤t, whered(u,v) is the distance (i.e., the minimum number of edges) between the verticesuandv. An optimalL(δ1,δ2,…,δt)‐coloring forGis one minimizing the largest integer used over all such colorings. Such a coloring problem has relevant applications in channel assignment for interference avoidance in wireless networks. This article presents efficient approximation algorithms forL(δ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)) andO(nt2δ1) time algorithms are proposed to find α‐approximate colorings on interval graphs and trees, respectively, wherenis the number of vertices and α is a constant depending ontand δ1,…,δt. Moreover, anO(n) time algorithm is given for theL(δ1,δ2)‐coloring of unit interval graphs, which provides a 3‐approximation. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 204–216 2007