Location-selection of Wireless Network Based on Restricted Steiner Tree Algorithm
作者单位：Zhengzhou Institute of Aeronautical Industry Management Zhengzhou Tourism College
会议名称：《2011 3rd International Conference on Environmental Science and Information Application Technology(ESIAT 2011)》
会议日期：2011年
学科分类：080904[工学-电磁场与微波技术] 0810[工学-信息与通信工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 080402[工学-测试计量技术及仪器] 0804[工学-仪器科学与技术] 081001[工学-通信与信息系统]
基 金：financial support from National Natural Sciences Foundation’s Youth Science Fund(10901144)
关 键 词：restricted Steiner tree computational complexity location-selection wireless network
摘 要：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 NPhard. 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.