Optimizing distance constraints frequency assignment with relaxation

Shao, Zehui; Zhu, Enqiang; Xu, Jin; Vesel, Aleksander; Zhang, Xiujun

RAIRO. Operations Research, Tome 55 (2021), pp. S1355-S1367

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].

Classification : 05C15, 05C90
Keywords: Frequency assignment, ($$)-relaxed $$(2, 1)-labeling, $$(2, 1)-labeling

B. Dai and W. Lin, On $(s,t)$-relaxed $L(2,1)$-labelings of the square lattice. Inf. Process. Lett. 113 (2013) 704–709. | MR | Zbl | DOI

B. Dai and W. Lin, On $(s,t)$-relaxed $L(2,1)$-labelings of the triangular lattice. J. Comb. Optim. 29 (2015) 655–669. | MR | Zbl | DOI

B. Dai and W. Lin, On $(s,t)$-relaxed $L(2,1)$-labelings of the hexagonal lattice. ARS Comb. 130 (2017) 319–331. | MR | Zbl

J. Fiala, T. Kloks and J. Kratochvíl, Fixed-parameter complexity of $\lambda$-labelings. Disc. Appl. Math. 113 (2001) 59–72. | MR | Zbl | DOI

J. R. Griggs and R. K. Yeh, Labelling graphs with a condition at distance 2. SIAM J. Disc. Math. 5 (1992) 586–595. | MR | Zbl | DOI

M. A. Henning and C. Löwnstein, Locating-total domination in claw-free cubic graphs. Disc. Math. 312 (2012) 3107–3116. | MR | Zbl | DOI

J. Kratochvíl, D. Kratsch and M. Liedloff, Exact algorithms for $L(2,1)$-labeling of graphs. In Vol. 4708 of Lecture Notes in Computer Science, Springer, Berlin-Heidelberg (2007) 513–524. | MR | Zbl | DOI

W. Lin, On $(s,t)$-relaxed $L(2,1)$-labeling of graphs. J. Comb. Optim. 31 (2014) 1–22. | MR | Zbl

C. Schwarz and D. S. Troxell,$L(2,1)$-labelings of products of two cycles. Disc. Appl. Math. 154 (2006) 1522–1540. | MR | Zbl | DOI

Z. Shao, R. K. Yeh, K. K. Poon and W. C. Shiu, The $L(2,1)$-labeling of $K_{1,n}$-free graphs and its applications. Appl. Math. Lett. 21 (2008) 1188–1193. | MR | Zbl | DOI

Z. Shao, A. Vesel and J. Xu, Frequency assignment problem in networks with limited spectrum. Cent. Eur. J. Oper. Res. 25 (2017) 699–723. | MR | Zbl | DOI

J. J. Sylvester, Mathematical questions with their solutions. Edu. Times 41 (1884) 171–178.

T. Zhao and G. Hu, A note on $(s,t)$-relaxed $L(2,1)$-labeling of graphs. J. Comb. Optim. 34 (2017) 378–382. | MR | Zbl | DOI