The strongly connecting problem on multihop packet radio networks

Abstract

[[abstract]]The problem of strongly connecting a multihop packet radio network by using a minimal total amount of transmission power is investigated. This problem is shown to be NP-complete. An approximation algorithm with the same computational complexity as that of finding a minimum spanning tree is given. It is also shown that the approximation algorithm can find a solution no greater than twice of the optimal solution. Experimental results show that the approximation solution may be close to the optimal solution.[[fileno]]2030210010035[[department]]資訊工程學