On an optimal algorithm for channel assignment in cellular networks

Arunabha Sen, Tom Roxborough, Bhabani P. Sinha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations


A cellular network is often modelled as a graph and the channel assignment problem is formulated as a coloring problem of the graph. Sen et al. (1998) introduced the notion of cellular graphs that models the hexagonal cell structure of a cellular network. Assuming a k-band buffering system where the interference does not extend beyond k cells away from the call originating cell, we provided two different formulations of the channel assignment problem: Distance-k chromatic number problem and k-band chromatic bandwidth problem. The channel assignment algorithms presented in Sen et al. were non-optimal. In this paper we provide: (i) a new algorithm for the distance-k chromatic number problem that is optimal and (ii) a near optimal algorithm for the 2-band chromatic bandwidth problem that has a performance bound of 4/3. The complexity of the algorithms is O(p), where p is the number of cells.

Original languageEnglish (US)
Title of host publicationIEEE International Conference on Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)078035284X
StatePublished - 1999
Event1999 IEEE International Conference on Communications, ICC 1999 - Vancouver, Canada
Duration: Jun 6 1999Jun 10 1999

Publication series

NameIEEE International Conference on Communications
ISSN (Print)1550-3607


Other1999 IEEE International Conference on Communications, ICC 1999

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On an optimal algorithm for channel assignment in cellular networks'. Together they form a unique fingerprint.

Cite this