Repository of University of Nova Gorica

Search the repository
A+ | A- | Help | SLO | ENG

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 1 / 1
First pagePrevious page1Next pageLast page
1.
No-hole λ-L (k, k – 1, …, 2,1)-labeling for square grid
Soumen Atta, Stanisław Goldstein, Priya Ranjan Sinha Mahapatra, 2017, original scientific article

Abstract: 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.
Keywords: graph labeling, labeling number, no-hole labeling, square grid, frequency assignment problem, approximation ratio
Published in RUNG: 17.04.2023; Views: 1979; Downloads: 0
This document has many files! More...

Search done in 0 sec.
Back to top