计算机科学 ›› 2017, Vol. 44 ›› Issue (Z11): 115-118.doi: 10.11896/j.issn.1002-137X.2017.11A.023
骆伟忠,蔡昭权,兰远东,刘运龙
LUO Wei-zhong, CAI Zhao-quan, LAN Yuan-dong and LIU Yun-long
摘要： 完全支配集是一个著名的NP难解问题,在无线传感器网络中具有重要应用。主要研究了能降低问题规模的规约化算法设计。通过对问题结构进行深入分析并对图中顶点进行着色,得到图中顶点之间的新的组合特性,在此基础上提出一系列高效的多项式时间的局部规约规则。证明了规约规则的正确性,并通过仿真实验验证了规约规则的有效性。
| [1] CHEN J,HE K,DU R,et al.Dominating Set and Network Co-ding-Based Routing in Wireless Mesh Networks[J].IEEE Transactions on Parallel and Distributed Systems,2015,26(2):423-433. [2] 路纲,周明天,唐勇,等.任意图支配集精确算法回顾[J].计算机学报,2010,33(6):1073-1087. [3] 马晨明,王万良,洪榛.无线传感器网络(k,m)-容错连通支配集的分布式构建[J].计算机科学,2016,43(1):128-133. [4] WANG D,ZHANG Q,LIU J.The self-pro-tection problem inwireless sensor networks[J].ACM Transactions on Sensor Networks (TOSN),2007,3:20. [5] WANG Y,LI X,ZHANG Q.Efficient algorithms for p-self-protection problem in static wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2008,19:1426-1438. [6] PFAFF J,LASKAR R C,HEDETNIEMI S T.NP-completeness of total and connected domination and irredundance for bipartite graphs[R].Clemson University,1983. [7] HE J,LIANG H.Complexity of total {k}-domination and rela-ted problems [C]// Proceedings of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management(FAW- AAIM).Berlin:Springer Berlin Heidelberg,2011:147-155. [8] ALBER J,NIEDERMEIER R.Improved tree decomposition basedalgorithms for domination-like problems[C]∥Proceedings of the 5th Latin American Symposium on Theoretical Informatics(LATIN’02).Berlin:Springer Berlin Heidelberg,2002:613-627. [9] ARCHDEACON D,ELLIS-MONAGHAN J,FISCHER D,et al.Some remarks on domination[J].Journal of Graph Theory,2004,46:207-210. [10] ZHAO W,WANG H,XU G.Totalk- domination number in gra-phs[J].International Journal of Pure and Applied Mathematics,2007,35(2):235-242. [11] 骆伟忠,冯启龙,王建新,等.完全p-支配集的参数算法[J].计算机学报,2013,36(9):1868-1879. [12] GANIAN R,SLIVOVSKY F,SZEIDER S,et al.Meta-kerne-lization with structural parameters[J].Journal of Computer and System Sciences,2016,82(2):333-346. |
| No related articles found! |
|
||
首页