The Thinnest Path Problem
The authors consider the thinnest path problem in wireless ad hoc networks. For a given source and a destination, the thinnest path problem asks for a path from the source to the destination that results in the minimum number of nodes overhearing the message. Such a path is achieved by carefully choosing a sequence of relaying nodes and their corresponding transmission power. At the first glance, one may wonder whether the thinnest path problem is simply a shortest path problem with the weight of each hop given by the number of nodes who can hear the message in this hop.