Approximate L(δ1, δ2, . . . , δt )-Coloring of Trees and Interval Graphs (Articolo in rivista)

Type
Label
  • Approximate L(δ1, δ2, . . . , δt )-Coloring of Trees and Interval Graphs (Articolo in rivista) (literal)
Anno
  • 2007-01-01T00:00:00+01:00 (literal)
Alternative label
  • Bertossi A. A.; Pinotti M. C. (2007)
    Approximate L(δ1, δ2, . . . , δt )-Coloring of Trees and Interval Graphs
    in Networks (N.Y.N.Y., Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Bertossi A. A.; Pinotti M. C. (literal)
Pagina inizio
  • 204 (literal)
Pagina fine
  • 216 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 49 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • In: Networks, vol. 49 (3) pp. 204 - 216. Wiley, 2007. (literal)
Note
  • ISI Web of Science (WOS) (literal)
Titolo
  • Approximate L(δ1, δ2, . . . , δt )-Coloring of Trees and Interval Graphs (literal)
Abstract
  • 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. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(3), 204-216 2007 (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it