Premium
Channel assignment and weighted coloring
Author(s) -
McDiarmid Colin,
Reed Bruce
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200009)36:2<114::aid-net6>3.0.co;2-g
Subject(s) - combinatorics , disjoint sets , fractional coloring , complete coloring , mathematics , lattice (music) , discrete mathematics , computer science , graph , graph power , physics , line graph , acoustics
In cellular telephone networks, sets of radio channels (colors) must be assigned to transmitters (vertices) while avoiding interference. Often, the transmitters are laid out like vertices of a triangular lattice in the plane. We investigated the corresponding weighted coloring problem of assigning sets of colors to vertices of the triangular lattice so that the sets of colors assigned to adjacent vertices are disjoint. We present a hardness result and an efficient algorithm yielding an approximate solution. © 2000 John Wiley & Sons, Inc.