Repository of University of Nova Gorica

Show document
A+ | A- | Help | SLO | ENG

Title:No-hole λ-L (k, k – 1, …, 2,1)-labeling for square grid
Authors:ID Atta, Soumen, Department of Computer Science and Engineering, University of Kalyani, Kalyani-741235, West Bengal, India (Author)
ID Goldstein, Stanisław, Faculty of Mathematics and Computer Science, University of Lodz, Banacha 22, PL-90-235 Lodz, Poland (Author)
ID Sinha Mahapatra, Priya Ranjan, Department of Computer Science and Engineering, University of Kalyani, Kalyani-741235, West Bengal, India (Author)
Files: This document has no files that are freely available to the public. This document may have a physical copy in the library of the organization, check the status via COBISS. Link is opened in a new window
Language:English
Work type:Not categorized
Typology:1.01 - Original Scientific Article
Organization:UNG - University of Nova Gorica
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
Year of publishing:2017
Number of pages:9-19
Numbering:3, 63
PID:20.500.12556/RUNG-8150 New window
COBISS.SI-ID:149321731 New window
DOI:10.26485/0459-6854/2017/67.3/1 New window
NUK URN:URN:SI:UNG:REP:UJZTOZLJ
Publication date in RUNG:17.04.2023
Views:1841
Downloads:0
Metadata:XML DC-XML DC-RDF
:
Copy citation
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Bulletin de la Société des Sciences et des Lettres de Łódź, Série: Recherches sur les déformations
Shortened title:Bull. Soc. Sci. Lettres Łódź Sér. Rech. Déform.
Publisher:Łódzkie Towarzystwo Naukowe, Stowarzyszenie, Poland
Year of publishing:2017
ISSN:0459-6854

Back