Given any fixed non-negative integer values h and k, the L(h, k)-labelling problem consists in an assignment of non-negative integers to the nodes of a graph such that adjacent nodes receive values which differ by at least h, and nodes connected by a 2-length path receive values which differ by at least k. The span of an L(h, k)-labelling is the difference between the largest and the smallest assigned frequency. The goal of the problem is to find out an L(h, k)-labelling with a minimum span. The L(h, k)-labelling problem has intensively been studied following many approaches and restricted to many special cases, concerning both the values of h and k and the considered classes of graphs. This paper reviews the results from previously published literature, looking at the problem with a graph algorithmic approach. It is an update of a previous survey written by the same author.
The L(h, k)-Labelling Problem: An Updated Survey and Annotated Bibliography / Calamoneri, Tiziana. - In: COMPUTER JOURNAL. - ISSN 0010-4620. - STAMPA. - 54:8(2011), pp. 1344-1371. [10.1093/comjnl/bxr037]
The L(h, k)-Labelling Problem: An Updated Survey and Annotated Bibliography
CALAMONERI, Tiziana
2011
Abstract
Given any fixed non-negative integer values h and k, the L(h, k)-labelling problem consists in an assignment of non-negative integers to the nodes of a graph such that adjacent nodes receive values which differ by at least h, and nodes connected by a 2-length path receive values which differ by at least k. The span of an L(h, k)-labelling is the difference between the largest and the smallest assigned frequency. The goal of the problem is to find out an L(h, k)-labelling with a minimum span. The L(h, k)-labelling problem has intensively been studied following many approaches and restricted to many special cases, concerning both the values of h and k and the considered classes of graphs. This paper reviews the results from previously published literature, looking at the problem with a graph algorithmic approach. It is an update of a previous survey written by the same author.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.