Abstract
Two problems are investigated. The first problem is to determine the minimal number of repeaters that should be allocated such that a multihop radio network can be strongly connected. As the number of repeaters to be used is determined and the repeaters are allocated, the second problem is to determine the power level that should be used for each repeater such that the network, now containing terminals and repeaters, is strongly connected and the total power levels used by these repeaters is minimum. The former problem is called the repeaters allocation problem (RAP) and the latter problem is called the power decision problem (PDP), respectively. It is shown that in the two-dimensional case both the problems are NP-hard. In the one-dimensional case an O(nlogn) optimal algorithm is also proposed to solve the RAP