Title :
The strongly connecting problem on multihop packet radio networks
Author :
Chen, Wen-Tsuen ; Huang, Nen-Fu
Author_Institution :
Inst. of Comput. & Decision Sci., Nat. Tsing Hua Univ., Taiwan
fDate :
3/1/1989 12:00:00 AM
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 :
computational complexity; frequency agility; packet switching; radio networks; trees (mathematics); approximation algorithm; computational complexity; minimum spanning tree; multihop packet radio networks; optimal solution; Adaptive equalizers; Bit error rate; Data communication; Delay; Indoor radio communication; Joining processes; Packet radio networks; Quadrature amplitude modulation; Radio transmitters; Spread spectrum communication;
Journal_Title :
Communications, IEEE Transactions on
