The L(2, 1)-labeling problem consists of assigning colors from the integer set 0 ...., lambda to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize lambda and it is in general NP-complete. In this paper the problem of L(2, 1)-labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a 3/2-approximate algorithm for L(2, 1)-labeling unigraphs is designed. This algorithm runs in 0(n) time, improving the time of the algorithm based on the greedy technique, requiring 0(m) time, that may be near to Theta (n(2)) for unigraphs. (C) 2011 Elsevier B.V. All rights reserved.

The L(2,1)-labeling of unigraphs / Calamoneri, Tiziana; Petreschi, Rossella. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 159:12(2011), pp. 1196-1206. [10.1016/j.dam.2011.04.015]

The L(2,1)-labeling of unigraphs

CALAMONERI, Tiziana;PETRESCHI, Rossella
2011

Abstract

The L(2, 1)-labeling problem consists of assigning colors from the integer set 0 ...., lambda to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize lambda and it is in general NP-complete. In this paper the problem of L(2, 1)-labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a 3/2-approximate algorithm for L(2, 1)-labeling unigraphs is designed. This algorithm runs in 0(n) time, improving the time of the algorithm based on the greedy technique, requiring 0(m) time, that may be near to Theta (n(2)) for unigraphs. (C) 2011 Elsevier B.V. All rights reserved.
2011
frequency assignment; l(2; 1)-labeling; unigraphs
01 Pubblicazione su rivista::01a Articolo in rivista
The L(2,1)-labeling of unigraphs / Calamoneri, Tiziana; Petreschi, Rossella. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 159:12(2011), pp. 1196-1206. [10.1016/j.dam.2011.04.015]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/33472
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 4
social impact