zbMATH — the first resource for mathematics

Channel assignment and weighted coloring. (English) Zbl 0971.90100
Summary: 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.

90C35 Programming involving graphs or networks
05C85 Graph algorithms (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Baldi, Comput Math Appl 19 pp 91– (1990) · Zbl 0687.05020 · doi:10.1016/0898-1221(90)90361-M
[2] Gamst, IEEE Trans Vehic Technol VT-35 pp 8– (1986) · doi:10.1109/T-VT.1986.24063
[3] and Computers and intractability, Freeman, San Francisco, 1979.
[4] Garey, Theor Comput Sci 1 pp 237– (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[5] and Graph imperfection, manuscript, 1999.
[6] and Graph imperfection II, manuscript, 1999.
[7] Griggs, J Combin Theory A 68 pp 169– (1994) · Zbl 0816.05027 · doi:10.1016/0097-3165(94)90096-5
[8] and Geometric algorithms and combinatorial optimization, Springer-Verlag, Berlin Heidelberg, 1988. · Zbl 0634.05001 · doi:10.1007/978-3-642-97881-4
[9] Hale, Proc IEEE 68 pp 1497– (1980) · doi:10.1109/PROC.1980.11899
[10] and (eds), Models and methods for radio channel assignment, Oxford University Press, Oxford, to appear.
[11] Jordan, ACM J Wireless Networks 2 pp 265– (1996) · doi:10.1007/BF01262046
[12] and On wireless spectrum estimation and generalized graph coloring, Proc 9th Ann Symp on Discrete Algorithms (SODA), 1998, pp. 383-393.
[13] MacDonald, Bell Syst Tech J 58 pp 15– (1979) · doi:10.1002/j.1538-7305.1979.tb02209.x
[14] Graph imperfection and channel assignment, to appear as a chapter in B.A. Reed, Perfect Graphs, Wiley, Chichester.
[15] and Static frequency assignment in cellular networks, Proc 4th Coll on Structural Information and Communications Complexity, July 1997.
[16] and Upper bounds for the span of triangular lattice graphs: Application to frequency planning for cellular networks, manuscript, 1999.
[17] van den Heuvel, J Graph Theory 29 pp 263– (1998) · Zbl 0930.05087 · doi:10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.