research unit 1

Publication

Type of publication:Article
Entered by:chita
Bibtex cite IDRACTI-RU1-2006-68
Journal Journal of Discrete Algorithms (JDA)
Year published 2006
Month September
Volume 4
Number 3
Pages 433-454
Note to appear
Keywords Approximation algorithms; Computational complexity; Radio networks; Frequency assignment; Coloring; Periodic graphs
Abstract
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. 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 discrete number of frequencies used is called order and the range of frequencies used, span. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span (min span RCP) or the order (min order RCP). In this paper, we deal with an interesting, yet not examined until now, variation of the radiocoloring problem: that of satisfying frequency assignment requests which exhibit some periodic behavior. In this case, the interference graph (modelling interference between transmitters) is some (infinite) periodic graph. Infinite periodic graphs usually model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they can model very large networks produced by the repetition of a small graph. A periodic graph G is defined by an infinite two-way sequence of repetitions of the same finite graph Gi(Vi,Ei). The edge set of G is derived by connecting the vertices of each iteration Gi to some of the vertices of the next iteration Gi+1, the same for all Gi. We focus on planar periodic graphs, because in many cases real networks are planar and also because of their independent mathematical interest. We give two basic results: • We prove that the min span RCP is PSPACE-complete for periodic planar graphs. • We provide an O(n(Ä(Gi)+ó)) time algorithm (where|Vi|=n, Ä(Gi) is the maximum degree of the graph Gi and ó is the number of edges connecting each Gi to Gi+1), which obtains a radiocoloring of a periodic planar graph G that approximates the minimum span within a ratio which tends to View the MathML source as Ä(Gi)+ó tends to infinity. We remark that, any approximation algorithm for the min span RCP of a finite planar graph G, that achieves a span of at most áÄ(G)+constant, for any á and where Ä(G) is the maximum degree of G, can be used as a subroutine in our algorithm to produce an approximation for min span RCP of asymptotic ratio á for periodic planar graphs.
Authors
Topics
BibTeXBibTeX
RISRIS
Attachments
 fulltext.pdf (main file)

Publication ID205