Approximate Capacity Subregions of Uniform Multihop Wireless Networks

The capacity region of multihop wireless network is involved in many capacity optimization problems. However, the membership of the capacity region is NP-complete in general, and hence the direct application of capacity region is quite limited. As a compromise, the authors often substitute the capacity region with a polynomial approximate capacity sub-region. Their construction exploits a nature of the wireless interference called strip-wise transitivity of independence discovered in this paper and utilize the independence polytopes of co-comparability graphs in a spatial-divide-conquer manner.