演講公告 90年11月26日 (星期一)

摘要

The channel assignment problem is to assign a channel (non-negative integer) to each radio transmitter so that interfering transmitters are assigned channels whose separation is not in a set of disallowed separations. Hale formulated this problem into the notion of T-coloring by constructing a graph G=(V,E) such that each vertex represents a transmitter and two vertices are adjacent if the corresponding transmitters are nearby. The interference of channels is modeled by a non-negative integral set T containing 0. Thus a valid channel assignment or T-coloring is a mapping f from the vertex set V to the set of all non-negative integers such that |f(x)=f(y)| \not\in T whenever xy \in E. The object of the problem is to find a T-coloring f such that the largest number in f(V) isminimized.In this talk, we give survey on the recent developments of this problem.