The Complexity of Optimal Addressing in Radio Networks
Sam Toueg, Ken Steiglitz · IRE Transactions on Communications Systems · 1982
We consider the complexity of finding optimal fixed- or variable-length unambiguous address codes for the nodes of a packet radio network. For fixed-length codes this problem is proved to be NP-complete, and its complexity for variable-length codes is still unknown. Some suboptimal heuristic algorithms are proposed.