2.
No-hole λ-L (k, k – 1, …, 2,1)-labeling for square gridSoumen Atta,
Stanisław Goldstein,
Priya Ranjan Sinha Mahapatra, 2017, izvirni znanstveni članek
Opis: Motivated by a frequency assignment problem, we demonstrate, for a fixed positive integer k, how to label an infinite square grid with a possibly small number of integer labels, ranging from 0 to λ −1, in such a way that labels of adjacent vertices differ by at least k, vertices connected by a path of length two receive values which differ by at least k − 1, and so on. The vertices which are at least k + 1 distance apart may receive the same label. By finding a lower bound for λ, we prove that the solution is close to optimal, with approximation ratio at most 9/8. The labeling presented is a no-hole one, i.e., it uses each of the allowed labels at least once.
Ključne besede: graph labeling, labeling number, no-hole labeling, square grid, frequency assignment problem, approximation ratio
Objavljeno v RUNG: 17.04.2023; Ogledov: 1961; Prenosov: 0
Gradivo ima več datotek! Več...
