A doubly cyclic channel assignment problem

✍ Scribed by Colin McDiarmid

• Book ID: 104294840
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 421 KB
• Volume: 80
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00094-2

✦ Synopsis

A standard model for radio channel assignment involves a set V of sites, the set (0, 1,2,. .} of channels, and a constraint matrix (w(u,v)) specifying minimum channel separations. An assignment f : V + {0,1,2,. . .} is feasible if the distance I.f(u) -f(u)1 b w(u, u) for each pair of sites u and u. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, . . , k -1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order r on the sites, and feasible assignments f must also satisfy f(ro)>f (v) for all except one site c. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, , k -1 are available then the distance between channels i and j is the minimum of /i ~ ,j\ and k -/i-j. We show how to find a corresponding optimal channel assignment in 0( 1 V / 3 ) steps.