IMPROVED ALGORITHM FOR MINIMUM COST RANGE ASSIGNMENT PROBLEM FOR LINEAR RADIO NETWORKS.

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³) time and O(n²) 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]