Channel Assignment in Wireless Networks and Classification of Minimum Graph Homomorphism
Tomás Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu · Electronic colloquium on computational complexity · 2006
We study the problem of assigning different communication channels to access points in a wireless Local Area Network. Each access point will be assigned a specific radio frequency channel. Since channels with similar frequencies interfer e, 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 Homomorphismproblem. We give a complete description of all possible approximation classes for the g eneral formulation of the problem.