L(h, 1, 1)-labeling of outerplanar graphs |
| |
Authors: | Tiziana Calamoneri Emanuele G. Fusco Richard B. Tan Paola Vocca |
| |
Affiliation: | (1) Dipartimento di Informatica, “Sapienza” Università di Roma, via Salaria, 113-00198 Rome, Italy;(2) Institute of Information and Computing Sciences, Utrecht University, Padualaan 14, 3584 CH Utrecht, The Netherlands;(3) Department of Computer Science, University of Sciences and Arts of Oklahoma, Chickasha, OK 73018, USA;(4) Dipartimento di Matematica “Ennio de Giorgi”, Università degli Studi del Salento, via Provinciale Lecce-Arnesano, P.O. Box 193, 73100 Lecce, Italy |
| |
Abstract: | An L(h, 1, 1)-labeling of a graph is an assignment of labels from the set of integers {0, . . . , λ} to the nodes of the graph such that adjacent nodes are assigned integers of at least distance h ≥ 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 λ, denoted by λ 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 Δ 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. This research is partially supported by the European Research Project Algorithmic Principles for Building Efficient Overlay Computers (AEOLUS) and was done during the visit of Richard B. Tan at the Department of Computer Science, University of Rome “Sapienza”, supported by a visiting fellowship from the University of Rome “Sapienza”. |
| |
Keywords: | Graph labeling Frequency assignment Condition at distance three |
本文献已被 SpringerLink 等数据库收录! |
|