Location-selection of Wireless Network Based on Restricted Steiner Tree Algorithm

The minimum Steiner tree problem has wide application background, such as transportation system, communication network, pipeline design and VISL, etc. It is unfortunately that the computational complexity of the problem is NP- hard. People are common to find some special problems to consider. In this paper, we introduce the definition of restricted Steiner tree problem, i.e., a restricted Steiner tree problem, which the fixed vertices are in the same side of one line L and we find a vertex on L such the distance of the tree is minimal. By the definition and the complexity of the Steiner tree problem, we know that the complexity of this problem is also Np-complete. Therefore, we consider there are two or three fixed vertices to find the restricted Steiner tree problem. We use the algorithm of restricted Steiner tree problem to solve the location-selection of wireless network.