Abstract | ||
---|---|---|
We study the power-assignment problem in radio networks, where each radio station can transmit in one of two possible power levels, corresponding to two ranges—short and long. We show that this problem is NP-hard, and we present an O(n2)-time assignment algorithm such that the number of transmitters that are assigned long range by the algorithm is at most (11/6) times the number of transmitters that are assigned long range by an optimal algorithm. We also present a (9/5)-approximation algorithm for this problem whose running time is considerably higher. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/s00453-006-1230-1 | Geometric Networks and Metric Space Embeddings |
Keywords | DocType | Volume |
Long Range,Power Level,Vertex Cover,Optimal Assignment,Communication Graph | Journal | 47 |
Issue | ISSN | Citations |
2 | 0178-4617 | 19 |
PageRank | References | Authors |
1.08 | 18 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paz Carmi | 1 | 321 | 43.14 |
Matthew J. Katz | 2 | 225 | 19.92 |
MJ Katz | 3 | 58 | 4.10 |