Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Fotakis, Dimitris Nikoletseas, Sotiris Papadopoulou, Vicky Spirakis, Paul G. dblp dblp dblp dblp Not MPG Author(s): Nikoletseas, Sotiris Papadopoulou, Vicky Spirakis, Paul G.
 Editor(s): Kucera, Ludek dblp Not MPII Editor(s): Kucera, Ludek
 BibTeX cite key*: FNPS02

 Title, Booktitle
 Title*: Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Range of Frequencies wg02.ps (372.11 KB) Booktitle*: Graph-Theoretic Concepts in Computer Science : 28th International Workshop, WG 2002

 Event, URLs
 URL of the conference: http://kam.mff.cuni.cz/~wg2002 URL for downloading the paper: Event Address*: Ceský Krumlov, Czech Republic Language: English Event Date* (no longer used): -- June 13-15, 2002 Organization: Event Start Date: 13 June 2002 Event End Date: 15 June 2002

 Publisher
 Name*: Springer URL: http://www.springer.de Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 2573 Number: Month: Pages: 223-234 Year*: 2002 VG Wort Pages: ISBN/ISSN: 3-540-00331-2 Sequence Number: DOI:

 (LaTeX) 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. The Radiocoloring (RC) of a graph $G(V, E)$ is an assignment function $\Phi : V \mapsto N$ such that $|\Phi(u) - \Phi(v)| \geq 2$, when $u, v$ are neighbors in $G$, and $|\Phi(u) - \Phi(v)| \geq 1$ when the distance of $u, v$ in $G$ is two. The range of frequencies used is called {\em span}. Here, we consider the optimization version of the Radiocoloring Problem (RCP) of finding a radiocoloring assignment of minimum span, called {\em min span RCP}. In this paper, we deal with a variation of RCP: that of satisfying frequency assignment requests with some {\em periodic} behavior. In this case, the interference graph is an (infinite) periodic graph. Infinite periodic graphs model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they may model very large networks produced by the repetition of a small graph. A {\em periodic graph $G$} is defined by an infinite two-way sequence of repetitions of the same finite graph $G_i(V_i, E_i)$. The edge set of $G$ is derived by connecting the vertices of each iteration $G_i$ to some of the vertices of the next iteration $G_{i+1}$, the same for all $G_i$. The model of periodic graphs considered here is similar to that of periodic graphs in Orlin [13], Marathe et al [10]. 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(\Delta(G_i) + \sigma))$ time algorithm, (where $|V_i| = n$, $\Delta(G_i)$ is the maximum degree of the graph $G_i$ and $\sigma$ is the number of edges connecting each $G_i$ to $G_{i+1})$, which obtains a radiocoloring of a periodic planar graph G that {\em approximates the minimum span within a ratio which tends to 2 as $\Delta(G_i) + \sigma$ tends to infinity}. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{FNPS02,
AUTHOR = {Fotakis, Dimitris and Nikoletseas, Sotiris and Papadopoulou, Vicky and Spirakis, Paul G.},
EDITOR = {Kucera, Ludek},
TITLE = {Radiocolorings in Periodic Planar Graphs: PSPACE-Completeness and Efficient Approximations for the Optimal Range of Frequencies},
BOOKTITLE = {Graph-Theoretic Concepts in Computer Science : 28th International Workshop, WG 2002},
PUBLISHER = {Springer},
YEAR = {2002},
VOLUME = {2573},
PAGES = {223--234},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Ceský Krumlov, Czech Republic},
ISBN = {3-540-00331-2},
}