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:Article
Entered by:
TitleRadiocoloring in planar graphs: Complexity and approximations
Bibtex cite IDRACTI-RU1-2005-49
Journal Theoretical Computer Science (TCS)
Year published 2005
Month August
Volume 340
Number 3
Pages 514-538
Keywords Mobile computing; Radio communication; Coloring; Computational complexity; Approximations; Planar graphs; Rapid mixing; Coupling
The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters, by exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function View the MathML source such that |Ö(u)-Ö(v)|greater-or-equal, slanted2, when u,v are neighbors in G, and |Ö(u)-Ö(v)|greater-or-equal, slanted1 when the distance of u,v in G is two. The number of discrete frequencies 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 radiocoloring problem for general graphs is hard to approximate (unless NP=ZPP) within a factor of n1/2-å (for any View the MathML source), where n is the number of vertices of the graph. However, when restricted to some special cases of graphs, the problem becomes easier. 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 where ëgreater-or-equal, slanted4Ä+50.
Fotakis, Dimitris
Nikoletseas, Sotiris
Papadopoulou, Viki
Spirakis, Paul
fulltext.pdf (main file)
Publication ID363