A Fast Exact Algorithm for Deployment of Sensor Nodes for Internet of Things

作     者：Zheng, Qinghua Ya, Chutong Yang, Haijun Zhou, Jianhe 

作者机构：Guangxi Univ Sci & Technol Sch Comp Sci Liuzhou 545006 Guangxi Peoples R China Univ Calif San Diego Jacobs Sch Engn San Diego CA 92093 USA Beihang Univ Sch Econ & Management Beijing 100191 Peoples R China Beihang Univ Beijing Adv Innovat Ctr Big Data & Brain Comp Beijing 100191 Peoples R China 

出 版 物：《INFORMATION SYSTEMS FRONTIERS》 (信息系统前沿)

年 卷 期：2020年第22卷第4期

页      面：829-842页

核心收录：

学科分类：0711[理学-系统科学] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 081101[工学-控制理论与控制工程] 0701[理学-数学] 071101[理学-系统理论] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [71771006  71171010] 

主　　题：Graph Minimal dominating set Exact algorithm State space search 

摘      要：The deployment problem of sensor nodes of Internet of things (IoT) can be abstracted as listing minimal dominating sets of a graph. The problem of listing all the minimal dominating sets in a graph can be converted to the problem of state space search among candidate vertex sets. The search and optimization technologies, such as the bidirectional search and branch cut, can be applied to solve the problem effectively. Our experiments show that the new algorithm can reduce the running time by at least an order of magnitude, compared to a state-of-the-art algorithm for listing all the minimal dominating sets.