Location
Toggle navigation
HOME
INSTITUTE
Mission
Address
Executive Board
Directorate
Scientific Advisory Board
Board of Trustees
NEWS
Press Releases
Awards
Spotlights
Campus Event Calendar
25th Anniversary
Employment
DEPARTMENTS
Algorithms & Complexity
Computer Vision and Machine Learning
Internet Architecture
Computer Grapics
Databases and Information Systems
Research Group Computational Biology
Automation of Logic
PUBLICATIONS
Algorithms & Complexity
Computer Vision and Multimodal Computing
Computer Grapics
Databases and Information Systems
Research Group Computational Biology
Automation of Logic
Research Reports
IMPRS-CS
PEOPLE
SOFTWARE
SERVICES
Joint Administration
- Information Services & Technology
- Building and Technical Support
- Library
- Public Relations
Research Coordination
Equal Opportunities
Care Appointees
Ombudsperson for
Good Scientific Practice
and Doctoral Research
International Office
CS@MPG
CS@SAAR
Computer Science Department,
Saarland University
Max Planck Institute for
Software Systems (MPI-SWS)
German Center for
Artificial Intelligence (DFKI)
Center for Security, Privacy
and Accountability (CISPA)
Graduate School for
Computer Science
Cluster of Excellence (MMCI)
Max Planck Center for Visual
Computing and Communication
Kaiserslautern-Saarbrücken
Computer Science Cluster
IT Incubator
Publications
Home
Intranet
Server
domino.mpi-inf.mpg.de
Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
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
Attachment(s)
:
wg02.ps (372.11 KB)
Booktitle*:
Graph-Theoretic Concepts in Computer Science : 28th International Workshop, WG 2002
Event, URLs
Conference URL::
http://kam.mff.cuni.cz/~wg2002
Downloading URL:
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:
Note, Abstract, ©
(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},
}
Entry last modified by Christine Kiesel, 03/02/2010
Edit History (please click the blue arrow to see the details)
Edit History (please click the blue arrow to see the details)
Editor(s)
Dimitris Fotakis
Created
02/03/2003 03:54:47 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Christine Kiesel
Christine Kiesel
Anja Becker
Anja Becker
Anja Becker
Edit Dates
27.08.2003 14:53:45
26.08.2003 15:05:14
20.06.2003 15:47:13
09.05.2003 12:25:25
04/09/2003 03:04:18 PM
Attachment Section
Attachment Section
wg02.ps
wg02.ps