Hardness results and efficient approximations for frequency assignment problems: Radio labelling and radio coloring

Citation
Da. Fotakis et al., Hardness results and efficient approximations for frequency assignment problems: Radio labelling and radio coloring, COMPUT INFO, 20(2), 2001, pp. 121-180
Citations number
95
Categorie Soggetti
Computer Science & Engineering
Journal title
COMPUTING AND INFORMATICS
ISSN journal
02320274 → ACNP
Volume
20
Issue
2
Year of publication
2001
Pages
121 - 180
Database
ISI
SICI code
0232-0274(2001)20:2<121:HRAEAF>2.0.ZU;2-J
Abstract
The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters, exploiting frequency reuse while kee ping signal interference to acceptable levels. The FAP is usually modeled b y variations of graph coloring. In this work we first survey the variations of the FAP and then we study two (similar but still different) frequency a ssignment problems: radio labelling and radiocoloring. For radio labelling, we prove that the problem is VP-complete for general g raphs and we provide efficient MC approximation algorithms. We also give a polynomial time algorithm computing an optimal radio labelling for planar g raphs, thus showing that radio labelling is in P for planar graphs. On the other hand, we prove that radiocoloring remains NP-complete even for planar graphs and we provide an efficient 2-ratio approximation algorithm. We als o present a fully polynomial randomized approximation scheme for computing the number of different radiocolorings of planar graphs.