计算机科学 ›› 2020, Vol. 47 ›› Issue (11A): 444-448.doi: 10.11896/jsjkx.200300023
王洪, 官礼和
WANG Hong, GUANG Li-he
摘要： 文中将粗糙集理论中的属性序引入到图论中,研究顶点序下图的支配集问题。首先,在图的顶点集上定义一个全序关系,称为顶点序。然后,利用顶点序定义一个二元等价关系,得到图中所有顶点闭邻接集的一个划分。最后,基于该划分设计了一种顶点序下图的极小支配集算法。同时,证明了该算法在给定顶点序下求解极小支配集的完备性和唯一性,并通过实例分析验证了所提算法的正确性和有效性。
中图分类号:
| [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 L.et 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] | 韩冰青, 陈一飞. 无线Ad Hoc网络中异构链表支配集算法 Heterogeneous Chain Dominating Set Algorithm in Wireless Ad Hoc Networks 计算机科学, 2018, 45(9): 135-140. https://doi.org/10.11896／j.issn.1002-137X.2018.09.021 |
| [2] | 骆伟忠,蔡昭权,兰远东,刘运龙. 完全支配集的规约算法 Reduction Algorithm for Total Dominating Set 计算机科学, 2017, 44(Z11): 115-118. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.023 |
| [3] | 印佳,程春玲,周剑. 基于极小独立支配集的多样化排序算法 Diverse Ranking Algorithm Based on Minimal Independent Dominating Set 计算机科学, 2017, 44(8): 181-186. https://doi.org/10.11896/j.issn.1002-137X.2017.08.032 |
| [4] | 马晨明,王万良,洪榛. 无线传感器网络(k,m)-容错连通支配集的分布式构建 Distributed Construction for (k,m)-Fault Tolerant Connected Dominating Set in Wireless Sensor Network 计算机科学, 2016, 43(1): 128-132. https://doi.org/10.11896/j.issn.1002-137X.2016.01.029 |
| [5] | 马晨明,王万良,洪榛. 无线传感器网络中一种改进的能效数据收集协议 Improved Energy Efficient Data Gathering Protocol in Wireless Sensor Network 计算机科学, 2015, 42(2): 65-69. https://doi.org/10.11896/j.issn.1002-137X.2015.02.014 |
| [6] | 江亮 刘建 鲜明 肖顺平. WSN中一种基于连通支配集的分簇一致性算法 Cluster-based Distributed Consensus Algorithms Based on Connected Dominating Set in WSN 计算机科学, 2012, 39(Z11): 55-57. |
| [7] | 任晓玲，白 雪，刘希玉. 粘贴模型在两类特殊问题中的改进算法研究 Improved Algorithm of Sticker Model in Two Special Problem 计算机科学, 2012, 39(Z11): 252-255. |
| [8] | 向永香，叶慧，李旻，陈卫东. OTIS网络的支配集问题算法研究 Algorithms for Dominating Set Problems in OTIS Networks 计算机科学, 2012, 39(3): 93-97. |
| [9] | 贺毅朝，田海燕，张新禄，高锁刚. 基于相邻矩阵快速构建虚拟主干网的近似算法 Fast Approximation Algorithm Based on Adjacent Matrix for Construction Virtual Backbone 计算机科学, 2012, 39(3): 83-87. |
| [10] | 李文翔,熊庆国,杨林涛. 一种实现高效副本发布与查询的DHT覆盖网 (School of information Science & Engineering, Wuhan University of Science & Technology, Wuhan 430081, China);(School of Electronics Information, Wuhan University, Wuhan 430079 , China) 计算机科学, 2010, 37(7): 87-90. |
| [11] | 王建新,陈蓓玮,陈建二. 支配问题的研究进展 Algorithms for Dominating Problems:A Survey 计算机科学, 2010, 37(2): 7-11. |
| [12] | 郭攀红,杨扬,李新友. 异构Ad hoc网络骨干网络的建立与性能分析 Backbone for Heterogeneous Ad hoc Networks and their Performance Analysis 计算机科学, 2009, 36(10): 101-103. |
| [13] | 罗光春 卢显良 李炯. 基于多层极小支配集聚类的WSN算法仿真与分析 计算机科学, 2008, 35(1): 34-37. |
| [14] | 李镇坚 葛启 王海涛 朱洪. 图的支配集若干问题的研究 计算机科学, 2007, 34(1): 177-178. |
| [15] | 马俊 朱洪. 带测度函数的连通支配集问题 计算机科学, 2006, 33(1): 220-222. |
|
||
首页