Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-040 | 6th March 2006 00:00

Channel assignment in wireless networks and classification of minimum graph homomorphism



We study the problem of assigning different communication channels to
acces points in a wireless Local Area Network. Each access point will
be assigned a specific radio frequency channel. Since channels with
similar frequencies interfere, it is desirable to assign far apart
channels (frequencies) to nearby access points. Our goal is to assign
the channels so as to minimize the overall interference experienced by
all access points. The above problem can be formulated as an instance
of the Minimum Graph Homomorphism problem. We give a complete
description of all possible approximation classes for the general
formulation of the problem.

ISSN 1433-8092 | Imprint