Some complexity results about packet radio networks (Corresp.)
- 1 July 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 30 (4) , 681-685
- https://doi.org/10.1109/tit.1984.1056928
Abstract
It is shown that the decision problem regarding the membership of a point in the capacity region of a packet radio network is nondeterministic polynomial time hard (NP hard). The capacity region is the set of all feasible origin-to-destination message rates where feasibility is defined as the existence of any set of rules for moving the data through the network so that the desired rates are satisfied.Keywords
This publication has 3 references indexed in Scilit:
- Two Interfering Queues in Packet-Radio NetworksIEEE Transactions on Communications, 1983
- The Complexity of Optimal Addressing in Radio NetworksIEEE Transactions on Communications, 1982
- Advances in packet radio technologyProceedings of the IEEE, 1978