research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleNP-Completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs
Bibtex cite IDRACTI-RU1-2000-8
Booktitle 25th International Symposium on Mathematical Foundations of Computer Science (MFCS 2000)
Series Lecture Notes in Computer Science (LNCS)
Year published 2000
Month August
Pages 363-372
Publisher Springer
The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. The Radiocoloring (RC) of a graph G(V,E) is an assignment function Φ: V → IN such that Φ(u)-Φ(v)≥ 2, when u; v are neighbors in G, and Φ(u)-Φ(v)≥1 when the minimum distance of u; v in G is two. The discrete number and the range of frequencies used are called order and span, respectively. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span or the order. In this paper we prove that the min span RCP is NP-complete for planar graphs. Next, we provide an O(nΔ) time algorithm (V = n) which obtains a radiocoloring of a planar graph G that approximates the minimum order within a ratio which tends to 2 (where Δ the maximum degree of G). Finally, we provide a fully polynomial randomized approximation scheme (fpras) for the number of valid radiocolorings of a planar graph G with λ colors, in the case λ ≥ 4λ + 50.
Fotakis, Dimitris
Nikoletseas, Sotiris
Papadopoulou, Viki
Spirakis, Paul
mfcs00.pdf (main file)
Publication ID323