Channel assignment problem and n-fold t-separated $$L(j_1,j_2,\ldots,j_m)$$ L ( j 1, j 2, …, j m ) -labeling of graphs

Wensong Lin () and Chenli Shen
Additional contact information
Wensong Lin: Southeast University
Chenli Shen: Southeast University

Journal of Combinatorial Optimization, 2018, vol. 35, issue 4, No 8, 1147-1167

Abstract: Abstract This paper considers the channel assignment problem in mobile communications systems. Suppose there are many base stations in an area, each of which demands a number of channels to transmit signals. The channels assigned to the same base station must be separated in some extension, and two channels assigned to two different stations that are within a distance must be separated in some other extension according to the distance between the two stations. The aim is to assign channels to stations so that the interference is controlled within an acceptable level and the spectrum of channels used is minimized. This channel assignment problem can be modeled as the multiple t-separated $$L(j_1,j_2,\ldots ,j_m)$$ L ( j 1 , j 2 , … , j m ) -labeling of the interference graph. In this paper, we consider the case when all base stations demand the same number of channels. This case is referred as n-fold t-separated $$L(j_1,j_2,\ldots ,j_m)$$ L ( j 1 , j 2 , … , j m ) -labeling of a graph. This paper first investigates the basic properties of n-fold t-separated $$L(j_1,j_2,\ldots ,j_m)$$ L ( j 1 , j 2 , … , j m ) -labelings of graphs. And then it focuses on the special case when $$m=1$$ m = 1 . The optimal n-fold t-separated L(j)-labelings of all complete graphs and almost all cycles are constructed. As a consequence, the optimal n-fold t-separated $$L(j_1,j_2,\ldots ,j_m)$$ L ( j 1 , j 2 , … , j m ) -labelings of the triangular lattice and the square lattice are obtained for the case $$j_1=j_2=\cdots =j_m$$ j 1 = j 2 = ⋯ = j m . This provides an optimal solution to the corresponding channel assignment problems with interference graphs being the triangular lattice and the square lattice, in which each base station demands a set of n channels that are t-separated and channels from two different stations at distance at most m must be $$j_1$$ j 1 -separated. We also study a variation of n-fold t-separated $$L(j_1,j_2,\ldots ,j_m)$$ L ( j 1 , j 2 , … , j m ) -labeling, namely, n-fold t-separated consecutive $$L(j_1,j_2,\ldots ,j_m)$$ L ( j 1 , j 2 , … , j m ) -labeling. And present the optimal n-fold t-separated consecutive L(j)-labelings of all complete graphs and cycles.

Keywords: Channel assignment problem; $$L(j_1; j_2; \ldots; j_m)$$ L ( j 1; j 2; …; j m ) -labeling number; n-fold $$L(j_1; j_2; \ldots; j_m)$$ L ( j 1; j 2; …; j m ) -labeling number; n-fold t-separated consecutive $$L(j_1; j_2; \ldots; j_m)$$ L ( j 1; j 2; …; j m ) -labeling number; Complete graph; Odd cycle; Triangular lattice; Square lattice (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-018-0255-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:4:d:10.1007_s10878-018-0255-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-018-0255-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().