Abstract
An arborescence of a multihop radio network is a directed spanning tree (with root x) such that the edges are directed away from the root. Based upon an arborescence, x can broadcast a message to other nodes according to the directed edges of the spanning tree. The minimum transmission power arborescence problem is to find an arborescence such that the message can be broadcasted to other nodes by using a minimal amount of transmission power. The minimum delay arborescence problem is to find an arborescence such that a message can be broadcasted to other nodes by using a minimal number of broadcast transmission. In this paper we show that both these problems are NP-complete. The reductions are from the maximum leaf spanning tree problem. A reverse arborescence is similar to an arborescence except that the edges are directed toward the root. Based upon a reverse arborescence, the root node can collect information from other nodes. In this paper we also show that the reverse minimum transmission power arborescence problem can be solved with the same computational complexity as that of finding a minimum cost spanning tree, and the reverse minimum delay arborescence problem can be solved with the same computational complexity as that of finding a spanning tree. © 1989 BIT Foundations.