Name
Abstract | ||
|---|---|---|
Given a set N of radio stations located on an Euclidean space, a source station s and an integer h(1¿h¿|N|¿1), the minimum bounded-hop broadcast range assignment problem consists in finding a range assignment for N of minimum total power consumption that allows broadcast operations from s to every station in N in at most h hops. The problem is known to be NP-hard on d-dimensional spaces for any d¿2 (18th Annual Symp. on Theoretical Aspects of Computer Science (STACS¿01), Lecture Notes in Computer Science, Vol. 1770, 2000, pp. 651¿660.) and some efficient approximation algorithms have been given in Clementi et al. and Wann et al. (18th Annual Symp. on Theoretical Aspects of Computer Science (STACS¿01), Lecture Notes in Computer Science, Vol. 1770, 2000, pp. 651¿660, IEEE INFOCOM¿01, 2001). In this paper, we address the case in which the stations are arbitrarily located along a line (i.e., the linear case). We provide the first polynomial-time algorithm that returns an optimal solution for any instance of the linear case. The algorithm works in O(h|N|2) time. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0304-3975(02)00538-8 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
algorithm work,theoretical aspects,integer h,minimum broadcast range assignment,linear multi-hop wireless network,set n,efficient approximation algorithm,lecture notes,linear case,ad hoc wireless networks,energy consumption,computer science,dynamic programming,annual symp,assignment problem | Journal | 299 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 26 |
PageRank | References | Authors |
1.18 | 15 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea E. F. Clementi | 1 | 1168 | 85.30 |
| Miriam di Ianni | 2 | 144 | 17.27 |
| Riccardo Silvestri | 3 | 1324 | 90.84 |