The minimal-power biconnecting problems on multihop radio networks

[[abstract]]©1990 Elsevier-Given a multihop radio network containing n terminals in the plane without obstacles, the minimal-power biconnecting problem (MBP) is to determine a `power-level' for each terminal, such that all the terminals are biconnected and the sum of the power levels is minimized. The constrained minimal-power biconnecting problem (CMBP) is similar to the MBP except that the n terminals are scattered over the plane with a set of obstacles such as mountains, buildings, etc. It is shown that both the above problems are NP-hard. An O(nlogn) approximation algorithm that produces a solution no greater than three times of that of an optimal solution is also proposed for the MBP. Experimental results show that in the average case, the approximate solution is close to the optimal solution[[department]]資訊工程學