L(h, 1)-labeling, h = 0, 1, 2, is a class of coloring problems arising from frequency assignment in radio networks, in which adjacent nodes must receive colors that are at least h apart while nodes connected by a two long path must receive different colors. This problem is NP-complete even when limited to planar graphs. Here, we focus on L(h, I)-labeling restricted to regular tilings of the plane and to outerplanar graphs. We give a unique parametric algorithm labeling each regular tiling of the plane. For these networks, a channel can be assigned to any node in constant time, provided that relative positions of the node in the network is locally known. Regarding outerplanar graphs with maximum degree Delta, we improve the best known upper bounds from Delta + 9, Delta + 5 and Delta + 3 to Delta + 3, Delta + 1 and Delta colors for the values of h equal to 2, 1 and 0, respectively, for sufficiently large values of Delta. For h = 0, 1 this result proves the polinomiality of the problem for outerplanar graphs. Finally, we study the special case Delta = 3, achieving surprising results. (C) 2003 Elsevier Inc. All rights reserved.

L(h, 1)-labeling subclasses of planar graphs / Calamoneri, Tiziana; Petreschi, Rossella. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - STAMPA. - 64:3(2004), pp. 414-426. [10.1016/j.jpdc.2003.11.005]

L(h, 1)-labeling subclasses of planar graphs

CALAMONERI, Tiziana;PETRESCHI, Rossella
2004

Abstract

L(h, 1)-labeling, h = 0, 1, 2, is a class of coloring problems arising from frequency assignment in radio networks, in which adjacent nodes must receive colors that are at least h apart while nodes connected by a two long path must receive different colors. This problem is NP-complete even when limited to planar graphs. Here, we focus on L(h, I)-labeling restricted to regular tilings of the plane and to outerplanar graphs. We give a unique parametric algorithm labeling each regular tiling of the plane. For these networks, a channel can be assigned to any node in constant time, provided that relative positions of the node in the network is locally known. Regarding outerplanar graphs with maximum degree Delta, we improve the best known upper bounds from Delta + 9, Delta + 5 and Delta + 3 to Delta + 3, Delta + 1 and Delta colors for the values of h equal to 2, 1 and 0, respectively, for sufficiently large values of Delta. For h = 0, 1 this result proves the polinomiality of the problem for outerplanar graphs. Finally, we study the special case Delta = 3, achieving surprising results. (C) 2003 Elsevier Inc. All rights reserved.
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: http://hdl.handle.net/11573/233691
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 60
  • ???jsp.display-item.citation.isi??? 48
social impact