CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishGiven two nonnegative integers h and k, an L(h, k)-labeling of a graph G = (V, E) is a map from V to a set of integer labels such that adjacent vertices receive labels at least h apart, while vertices at distance at most 2 receive labels at least k apart. The goal of the L(h, k)-labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the L(h, k)-labeling problem is NP-complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co-comparability graphs, its subclass of interval graphs, and circular-arc graphs. To the best of our knowledge, ours is the first reported result concerning the L(h, k)-labeling of co-comparability and circular-arc graphs. In particular, we provide the first algorithm to L(h, k)-label co-comparability, interval, and circular-arc graphs with a bounded number of colors. Finally, in the special case where k = 1 and G is an interval graph, our algorithm improves on the best previously-known ones using a number of colors that is at most twice the optimum.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | On the L(h,k)-Labeling Co-Comparability Graphs and Circular-Arc Graphs |
| Autori: | |
| Data di pubblicazione: | 2009 |
| Rivista: | |
| Handle: | http://hdl.handle.net/11573/33466 |
| Appartiene alla tipologia: | 01a Articolo in rivista |
File allegati a questo prodotto
http://hdl.handle.net/11573/33466
Copyright © 2020