The strongly connecting problem on multihop packet radio networks
- 1 March 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 37 (3) , 293-295
- https://doi.org/10.1109/26.20105
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]]資訊工程學This publication has 13 references indexed in Scilit:
- Optimal Transmission Ranges for Randomly Distributed Packet Radio TerminalsIEEE Transactions on Communications, 1984
- The Design and Simulation of a Mobile Radio Network with Distributed ControlIEEE Journal on Selected Areas in Communications, 1984
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983
- A Distributed Routing Design for a Broadcast EnvironmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- The Architectural Organization of a Mobile Radio Network via a Distributed AlgorithmIEEE Transactions on Communications, 1981
- Recognition and Self-Organization of Nodes into DTDMA NetsIEEE Transactions on Aerospace and Electronic Systems, 1981
- Approximation Algorithms for Several Graph Augmentation ProblemsSIAM Journal on Computing, 1981
- Finding Minimum Spanning TreesSIAM Journal on Computing, 1976
- Augmentation ProblemsSIAM Journal on Computing, 1976
- An 0(|E|loglog|V|) algorithm for finding minimum spanning treesInformation Processing Letters, 1975