Name
Title | ||
|---|---|---|
Hardness Results And Efficient Approximations For Frequency Assignment Problems: Radio Labelling And Radio Coloring |
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 modeled by variations of graph coloring. In this work we first survey the variations of the FAP and then we study two (similar but still different) frequency assignment problems: radio labelling and radiocoloring.For radio labelling, we prove that the problem is VP-complete for general graphs and we provide efficient MC approximation algorithms. We also give a polynomial time algorithm computing an optimal radio labelling for planar graphs, thus showing that radio labelling is in P for planar graphs. On the other hand, we prove that radiocoloring remains NP-complete even for planar graphs and we provide an efficient 2-ratio approximation algorithm. We also present a fully polynomial randomized approximation scheme for computing the number of different radiocolorings of planar graphs. |
Year | Venue | Keywords |
|---|---|---|
2001 | COMPUTING AND INFORMATICS | mobile computing, radio networks, coloring, computational complexity, approximations, planar graphs, rapid mixing, coupling |
Field | DocType | Volume |
Approximation algorithm,Transmitter,Discrete mathematics,Polynomial,Computer science,Algorithm,Frequency assignment,Time complexity,Planar graph,Graph coloring,Computational complexity theory | Journal | 20 |
Issue | ISSN | Citations |
2 | 1335-9150 | 3 |
PageRank | References | Authors |
0.43 | 6 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitris Fotakis | 1 | 570 | 59.07 |
| Sotiris E. Nikoletseas | 2 | 1027 | 107.41 |
| Vicky G. Papadopoulou | 3 | 85 | 7.94 |
| Paul G. Spirakis | 4 | 2222 | 299.05 |