An L(h, 1, 1)-labeling of a graph is an assignment of labels from the set of integers {0, . . . , lambda} to the nodes of the graph such that adjacent nodes are assigned integers of at least distance h a parts per thousand yen 1 apart and all nodes of distance three or less must be assigned different labels. The aim of the L(h, 1, 1)-labeling problem is to minimize lambda, denoted by lambda (h, 1, 1) and called span of the L(h, 1, 1)-labeling. As outerplanar graphs have bounded treewidth, the L(1, 1, 1)-labeling problem on outerplanar graphs can be exactly solved in O(n (3)), but the multiplicative factor depends on the maximum degree Delta and is too big to be of practical use. In this paper we give a linear time approximation algorithm for computing the more general L(h, 1, 1)-labeling for outerplanar graphs that is within additive constants of the optimum values.

L(h, 1, 1)-labeling of outerplanar graphs / Calamoneri, Tiziana; Fusco, EMANUELE GUIDO; Richard B., Tan; Paola, Vocca. - In: MATHEMATICAL METHODS OF OPERATIONS RESEARCH. - ISSN 1432-2994. - STAMPA. - 69:2(2009), pp. 307-321. (Intervento presentato al convegno 5th Cologne-Twente Workshop on Graphs and Combinatorial Optimization tenutosi a Lambrecht, GERMANY nel JUN 05-09, 2006) [10.1007/s00186-008-0261-6].

L(h, 1, 1)-labeling of outerplanar graphs

CALAMONERI, Tiziana;FUSCO, EMANUELE GUIDO;
2009

Abstract

An L(h, 1, 1)-labeling of a graph is an assignment of labels from the set of integers {0, . . . , lambda} to the nodes of the graph such that adjacent nodes are assigned integers of at least distance h a parts per thousand yen 1 apart and all nodes of distance three or less must be assigned different labels. The aim of the L(h, 1, 1)-labeling problem is to minimize lambda, denoted by lambda (h, 1, 1) and called span of the L(h, 1, 1)-labeling. As outerplanar graphs have bounded treewidth, the L(1, 1, 1)-labeling problem on outerplanar graphs can be exactly solved in O(n (3)), but the multiplicative factor depends on the maximum degree Delta and is too big to be of practical use. In this paper we give a linear time approximation algorithm for computing the more general L(h, 1, 1)-labeling for outerplanar graphs that is within additive constants of the optimum values.
2009
condition at distance three; frequency assignment; graph labeling
01 Pubblicazione su rivista::01a Articolo in rivista
L(h, 1, 1)-labeling of outerplanar graphs / Calamoneri, Tiziana; Fusco, EMANUELE GUIDO; Richard B., Tan; Paola, Vocca. - In: MATHEMATICAL METHODS OF OPERATIONS RESEARCH. - ISSN 1432-2994. - STAMPA. - 69:2(2009), pp. 307-321. (Intervento presentato al convegno 5th Cologne-Twente Workshop on Graphs and Combinatorial Optimization tenutosi a Lambrecht, GERMANY nel JUN 05-09, 2006) [10.1007/s00186-008-0261-6].
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/124254
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact