Frequency assignment in mobile and radio networks
Dimitris A. Fotakis, Grammati E. Pantziou, George P. Pentaris, Paul G. Spirakis · DIMACS series in discrete mathematics and theoretical computer science · 1998
. We deal with the problem of frequency assignment in mobile and general radio networks, where the signal interferences are modeled using an interference graph G. Our approach uses graph theoretic and optimization techniques. We first study on-line algorithms for frequency assignment in mobile networks. We prove that the greedy algorithm is \\Delta-competitive, where \\Delta is the maximum degree of G. We next employ the "classify and randomly select" paradigm to give a 5-competitive randomized algorithm for the case of planar interference graphs. We also show how the problem of on-line frequency assignment in mobile networks with multiple available frequency channels reduces to the problem of on-line frequency assignment in mobile networks with a single channel. We continue to study radio coloring and radio labeling as combinatorial models for frequency assignment in general radio networks. In both problems, the objective is to minimize the maximum frequency channel used, w...