The strongly connecting problem on multihop packet radio networks |
| |
| Authors: | Chen W.-T. Huang N.-F. |
| |
| Affiliation: | Inst. of Comput. & Decision Sci., Nat. Tsing Hua Univ.; |
| |
| 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 that of the optimal solution. Experimental results show that the approximation solution may be close to the optimal solution |
| |
| Keywords: | |
|
|
