Volume 55, 2021Regular articles published in advance of the transition of the journal to Subscribe to Open (S2O). Free supplement sponsored by the Fonds National pour la Science Ouverte
|Page(s)||S1355 - S1367|
|Published online||02 March 2021|
Optimizing distance constraints frequency assignment with relaxation
Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, P.R. China
2 School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, P.R. China
3 Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, Maribor 2000, Slovenia
4 School of Information Science and Engineering, Chengdu University, Chengdu 610106, P.R. China
* Corresponding author: firstname.lastname@example.org
Accepted: 28 April 2020
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].
Mathematics Subject Classification: 05C15 / 05C90
Key words: Frequency assignment / (s, t)-relaxed L(2, 1)-labeling / L(2, 1)-labeling
© EDP Sciences, ROADEF, SMAI 2021
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.