http://www.cnr.it/ontology/cnr/individuo/prodotto/ID43969
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
- Pagina fine
- Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
- 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 graphstrees, 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