Optimizing distance constraints frequency assignment with relaxation

¹ Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, P.R. China
² School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, P.R. China
³ Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, Maribor 2000, Slovenia
⁴ School of Information Science and Engineering, Chengdu University, Chengdu 610106, P.R. China

^* Corresponding author: aleksander.vesel@um.si

Received: 12 February 2018
Accepted: 28 April 2020

Abstract

In a typical wireless telecommunication network, a large number of communication links is established with a limited number of available frequencies. The problem that addresses assigning available frequencies to transmitters such that interference is avoided as far as possible is called the frequency assignment problem. The problem is usually modeled as a graph coloring (labeling) problem. We study in this paper the (s, t)-relaxed L(2, 1)-labeling of a graph which considers the situation where transceivers that are very close receive frequencies that differ by at least two while transceivers that are close receive frequencies that differ by at least one. In addition, the model allows at most s (resp. t) anomalies at distance one (resp. two). The objective of the model is to minimize the span of frequencies in a corresponding network. We show that it is NP-complete to decide whether the minimal span of a (1, 0)-relaxed L(2, 1)-labeling of a graph is at most k. We also prove that the minimal span of this labeling for two classes of graphs is bounded above with the the square of the largest degree in the graph of interest. These results confirm Conjecture 6 and partially confirm Conjecture 3 stated in Lin [J. Comb. Optim. 31 (2016) 1–22].