Computer Science ›› 2020, Vol. 47 ›› Issue (11A): 444-448.doi: 10.11896/jsjkx.200300023

• Big Data & Data Science • Previous Articles     Next Articles

Dominating Set Algorithm for Graphs Based on Vertex Order

WANG Hong, GUANG Li-he   

  1. School of Mathematics and Statistics,Chongqing Jiaotong University,Chongqing 400074,China
  • Online:2020-11-15 Published:2020-11-17
  • About author:WANG Hong,born in 1995,postgra-duate.His main research interests include rough set theory,graph theory and its applications.
    GUAN Li-he,born in 1975,Ph.D,associate professor.His main research inte-rests include rough set,data mining and knowledge acquisition.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61573076) and Chongqing ScienceTechnology Commission Project (cstc2015shmszx30004).

Abstract: This paper introduces the attribute order in rough set theory into graph theory,and studies the dominating set problem of undirected graphs based on vertex order.First,a total order relation is defined on the vertex set of graph,which is called vertex order.Then,a binary equivalence relation is defined by using the vertex order,and a partition of closed sets of all vertices in graph is obtained.Finally,based on the partition,a minimal dominating set algorithm for graphs under vertex order is designed.At the same time,it proves the completeness and uniqueness of this algorithm for solving the minimum dominating set under a given vertex order.An example is used to show the correctness and effectiveness of the algorithm.

Key words: Dominating set, Vertex order, Algorithm completeness, Algorithm uniqueness

CLC Number: 

  • TP18
[1] PAREKH A K.Analysis of a greedy heuristic for finding smalldominating sets in graphs [J].Information Processing Letters,1991,39(5):237-240.
[2] SHEN C,LI T.Multi-document summarization via the minimumdominating set [C]//Proceedings of the 23rd International Conference on Computational Linguistics.Association for Computational Linguistics,Stroudsburg,PA,USA,2010:984-992.
[3] DINH T N,SHEN Y,NGUYEN D T,et al.On the approxi-mability of positive influence dominating set in social networks [J].Journal of Combinatorial Optimization,2014,27(3):487-503.
[4] BORIA N,MURAT C,PASCHOS V T.The probabilistic minimum dominating set problem [J].Discrete Applied Mathema-tics,2018,234:93-113.
[5] CHINNASAMY A,SIVAKUMAR B,SURESH A,et al.Minimum connected dominating set based RSU allocation for smartCloud vehicles in VANET [J].Cluster Computing,2019,22:S12795-S12804.
[6] HANAKA T,NISHIMURA N,ONO H.On directed coveringand domination problems [J].Discrete Applied Mathematics,2019,259:76-99.
[7] LU G,ZHOU M T,TANG Y,et al.A survey on exact algorithms for dominating set related problems in arbitrary graphs [J].Chinese Journal of Computer,2010,33(6):121-135.
[8] LIN M C,MIZRAHI M J,SZWARCFITER J L.Exact algo-rithms for minimum weighted dominating induced matching [J].Algorithmica,2017,77(3):642-660.
[9] ZHOU X Q,YE A S,ZHANG Z Q.Exact algorithm for connected dominating set in undirected graphs [J].Application Research of Computers,2019,36(9):2569-2574.
[10] LIN G,ZHU W X,ALI M M.An effective hybrid memetic algorithm for the minimum weight dominating set problem [J].IEEE Transactions on Evolutionary Computation,2016,20(6):892-907.
[11] ABED S A,RAIS H M.Hybrid bat algorithm for minimumdominating set problem [J].Journal of Intelligent and Fuzzy Systems,2017,33(4):2329-2339.
[12] YUAN F Y,LI C X,GAO X,et al.A novel hybrid algorithm for minimum total dominating set problem [J].Mathematics,2019,7(3):222-232.
[13] JIA L J,RAJARAMAN R,SUEL T.An efficient distributed algorithm for constructing small dominating sets [J].Distributed Computing,2002,15(4):193-205.
[14] JALLU R K,PRASAD P R,DAS G K.Distributed construction of connected dominating set in unit disk graphs [J].Journal of Parallel and Distributed Computing,2017,104:159-166.
[15] HJULER N,ITALIANO G F,PAROTSIDIS N,et al.Dominating sets and connected dominating sets in dynamic graphs [C]//Proceedings of the 36th International Symposium on Theo-retical Aspects of Computer Science (STACS 2019).Editors:Niedermeier R and Paul C,2019:1-35.
[16] BOYAR J,EIDENBENZ S J,FAV RHOOLDT LM,et al.Online dominating set [J].Algorithmica,2019,81:1938-1964.
[17] PRADHAN D,JHA A.On computing a minimum secure dominating set in block graphs [J].Journal of Combinatorial Optimization,2018,35:613-631.
[18] ADAWIYAH R,AGUSTIN I H,DAFIK,et al.Related wheelgraphs and its locating edge domination number [J].Journal of Physics Conference Series,2018,1022:1-8.
[19] SUKHAMAY K.Relationship between optimal k-distance dominating sets in a weighted graph and its spanning trees [J].Information Processing Letters,2019,147:3-5.
[20] HAYNES T W,HEDETNIEMI S T,SLATER P J.Fundamentals of domination in graphs [M].New York,USA:Marcel Dekker,1998.
[21] PAWLAK Z.Rough sets [J].International Journal of Information & Computer Sciences,1982,11:341-356.
[22] WANG S P,ZHU Q X,ZHU W,et al.Equivalent characterizations of some graph problems by covering-based rough sets [J].Journal of Applied Mathematics,2013,2013:1-7.
[23] CATTANEO G,CHIASELOTTI G,CIUCCI D,et al.On theconnection of hypergraph theory with formal concept analysis and rough set theory [J].Information Sciences,2016,330(2):342-357.
[24] XU T H,WANG G Y.Finding strongly connected components of simple digraphs based on generalized rough sets theory [J].Knowledge-Based Systems,2018,149:88-98.
[25] CHEN J K,LIN Y J,LIN G P,et al.The relationship between attribute reducts in rough sets and minimal vertex covers of graphs [J].Information Sciences,2015,325:87-97.
[26] CHEN J K,LIN Y J,LI J J,et al.A rough set method for the minimum vertex cover problem of graphs [J].Applied Soft Computing,2016,42:360-367.
[27] XU Q Y,TAN A H,LI J J.A rough set method for the vertex cover problem in graph theory [J].Journal of Intelligent & Fuzzy Systems,2016,30:2003-2013.
[28] TAN A H,TAO Y Z,WANG C.A rough-set based solution of the total domination problem [C]//Polkowski al.(eds) Rough Sets.IJCRS 2017.Lecture Notes in Computer Science,vol 10313,Springer,Cham,2017:131-139.
[29] TAN A H,LI J J,CHEN J K,et al.An Attribute ReductionMethod Based on Rough Sets for Dominating Sets of Graph [J].Pattern Recognition and Artificial Intelligence,2015,28(6):507-512.
[30] WANG J,WANG J.Reduction algorithms based on discernibility matrix:The order attributes method [J].Journal of Computer Science and Technology,2001,16(6):489-504.
[31] HU F,WANG G Y.Quick reduction algorithm basedon attributes order [J].Chinese Journal of Computer,2007,30(8):1429-1435.
[32] HAN S Q,ZHAO M.Reduct Theory [M].Beijing:TsinghuaUniversity Press,2010:65-264.
[33] GUAN L H,WANG G Y,HU F.A decision rules mining algorithm based on attribute order [J].Control and Decision,2012,27(2):313-316.
[1] YI Meng, LIANG Jia-rong, QIN Bin. Approximate Algorithm for Minimum Virtual Backbone in 3D Wireless Ad Hoc Networks [J]. Computer Science, 2020, 47(7): 250-256.
[2] HAN Bing-qing, CHEN Yi-fei. Heterogeneous Chain Dominating Set Algorithm in Wireless Ad Hoc Networks [J]. Computer Science, 2018, 45(9): 135-140.
[3] ZHANG Xiu-jun, WU Pu, YANG Hong and SHAO Ze-hui. Linear-time Algorithm for Weighted Domination Problem of Strongly Chordal Graph Based on Local Ratio Method [J]. Computer Science, 2017, 44(Z6): 129-132.
[4] LUO Wei-zhong, CAI Zhao-quan, LAN Yuan-dong and LIU Yun-long. Reduction Algorithm for Total Dominating Set [J]. Computer Science, 2017, 44(Z11): 115-118.
[5] YIN Jia, CHENG Chun-ling and ZHOU Jian. Diverse Ranking Algorithm Based on Minimal Independent Dominating Set [J]. Computer Science, 2017, 44(8): 181-186.
[6] MA Chen-ming, WANG Wan-liang and HONG Zhen. Improved Energy Efficient Data Gathering Protocol in Wireless Sensor Network [J]. Computer Science, 2015, 42(2): 65-69.
[7] . Improved Algorithm of Sticker Model in Two Special Problem [J]. Computer Science, 2012, 39(Z11): 252-255.
[8] . Cluster-based Distributed Consensus Algorithms Based on Connected Dominating Set in WSN [J]. Computer Science, 2012, 39(Z11): 55-57.
[9] . Algorithms for Dominating Set Problems in OTIS Networks [J]. Computer Science, 2012, 39(3): 93-97.
[10] . Fast Approximation Algorithm Based on Adjacent Matrix for Construction Virtual Backbone [J]. Computer Science, 2012, 39(3): 83-87.
[11] LI Wen-xiang,XIONG Qing-guo,YANG Lin-tao. (School of information Science & Engineering, Wuhan University of Science & Technology, Wuhan 430081, China);(School of Electronics Information, Wuhan University, Wuhan 430079 , China) [J]. Computer Science, 2010, 37(7): 87-90.
[12] WANG Jian-xin,CHEN Bei-wei,CHEN Jian-er. Algorithms for Dominating Problems:A Survey [J]. Computer Science, 2010, 37(2): 7-11.
[13] GUO Pan-hong, YANG Yang,LI Xin-you. Backbone for Heterogeneous Ad hoc Networks and their Performance Analysis [J]. Computer Science, 2009, 36(10): 101-103.
[14] LI Zhen-Jian, GE Qi ,WANG Hai-Tao ,ZHU Hong (Dept. of Computer Science and Engineering, Fudan University,Shanghai 200433). [J]. Computer Science, 2007, 34(1): 177-178.
[15] MA Jun, ZHU Hong (Laboratory for Intelligent Information Processing, Fudan University, Shanghai 200433). [J]. Computer Science, 2006, 33(1): 220-222.
Full text



[1] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[2] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[3] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[4] YANG Yu-qi, ZHANG Guo-an and JIN Xi-long. Dual-cluster-head Routing Protocol Based on Vehicle Density in VANETs[J]. Computer Science, 2018, 45(4): 126 -130 .
[5] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[6] GUO Jun-xia, GUO Ren-fei, XU Nan-shan and ZHAO Rui-lian. Study on Construction of EFSM Model for Web Application Based on Session[J]. Computer Science, 2018, 45(4): 203 -207 .
[7] WANG Zhen-wu, LV Xiao-hua and HAN Xiao-hui. Survey of Terrain LOD Technology Based on Quadtree Segmentation[J]. Computer Science, 2018, 45(4): 34 -45 .
[8] CUI Jian-jing, LONG Jun, MIN Er-xue, YU Yang and YIN Jian-ping. Survey on Application of Homomorphic Encryption in Encrypted Machine Learning[J]. Computer Science, 2018, 45(4): 46 -52 .
[9] ZHANG Yu, GAO Ke-ning, YU Ge. Method of Link Prediction in Social Networks Using Node Attribute Information[J]. Computer Science, 2018, 45(6): 41 -45 .
[10] WANG Zhan-bing, SONG Wei, PENG Zhi-yong, YANG Xian-di, CUI Yi-hui, SHEN Yuan. Subsequence Outsourcing Query Method over Encrypted Genomic Data[J]. Computer Science, 2018, 45(6): 51 -56 .