TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1995

COGA 5-Wheel

Page Content

to Navigation

Preprints 1995

List Coloring and Optimization Criteria for a Channel Assignment Problem
Citation key Report-458-1995
Author Ewa Malesi\'nska
Title of Book Proceedings of the ACM International Conf. on Mobile Computing and Networking
Pages 210-217
Year 1995
Number 458
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe