Computer Science ›› 2017, Vol. 44 ›› Issue (Z11): 115-118.doi: 10.11896/j.issn.1002-137X.2017.11A.023

Previous Articles     Next Articles

Reduction Algorithm for Total Dominating Set

LUO Wei-zhong, CAI Zhao-quan, LAN Yuan-dong and LIU Yun-long   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Total dominating set is a famous NP-hard problem,and has important applications in wireless sensor networks.In this paper,we mainly studied the design of reduction algorithm which can reduce the size of the original pro-blem.By analyzing the problem structure and coloring the vertices in given graph,we observed many new combinatorial properties of its vertices,and presented a set of efficient and polynomial-time reduction rules exploring local structures of the graph.The rules are proved to be correct theoretically,and the effectiveness is verified by simulations.

Key words: Total dominating set,NP-hard,Reduction,Black and white coloring

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!