Back to Search
Start Over
IMPROVED ALGORITHM FOR MINIMUM COST RANGE ASSIGNMENT PROBLEM FOR LINEAR RADIO NETWORKS.
- Source :
- International Journal of Foundations of Computer Science; Jun2007, Vol. 18 Issue 3, p619-635, 17p, 7 Diagrams
- Publication Year :
- 2007
-
Abstract
- In the unbounded version of the range assignment problem for all-to-all communication in 1D, a set of n radio-stations are placed arbitrarily on a line; the objective is to assign ranges to these radio-stations such that each of them can communicate with the others (using at most n - 1 hops) and the total power consumption is minimum. A simple incremental algorithm for this problem is proposed which produces optimum solution in O(n<superscript>3</superscript>) time and O(n<superscript>2</superscript>) space. This is an improvement in the running time by a factor of n over the best known existing algorithm for the same problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 18
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 25075361
- Full Text :
- https://doi.org/10.1142/S0129054107004863