Title
List Coloring and Optimization Criteria for a Channel
Assignment Problem
Author
Ewa Malesinska
Publication
Proceedings of the ACM International Conf. on Mobile
Computing and Networking, 1995, pp. 210-217
Source
-
Classification
-
not available
Keywords
-
not available
-
-
This paper introduces a channel assignment problem in
mixed cellular telephone networks consisting of both
dynamic and fixed base stations. In mixed networks
radio channels have to be allocated to the fixed
stations in such a way that enough freedom is left for
dynamic transmitters. We discuss some possibilities of
evaluating fixed assignment plans and propose two
optimization criteria, which form a generalization of
list coloring and T-coloring problems. We give a
complete analysis of the computational complexity of
these criteria in the case when the dynamic part of the
network can be modeled as a graph with bounded
treewidth or as a graph whose every connected component
is complete or almost complete.
