|
|
|
| An Attribute Reduction Method Based on Rough Sets for Dominating Sets of Graph |
| TAN An-Hui1,2, LI Jin-Jin2, CHEN Jin-Kun2, LIN Guo-Ping2 |
1.School of Mathematical Sciences, Xiamen University, Xiamen 361005
2.School of Mathematics and Statistics, Minnan Normal University, Zhangzhou 363000 |
|
|
|
|
Abstract The relationship between attribute reduction problem in rough sets and dominating set problem in graph is discussed. By constructing an information system, the attribute reduction problem in rough sets is associated with the dominating set problem in graph, so as to transformed the dominating set problem into the attribute reduction problem. Firstly, it is proved that the minimal dominating set of a graph is exactly the attribute reduction of the constructed information system. Then, a minimum dominating set algorithm based on information entropy is proposed. Finally, A practical example illustrates the feasibility and efficiency of the proposed algorithm.
|
|
Received: 03 March 2014
|
|
|
|
|
|
[1] Pawlak Z. Rough Sets. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356
[2] Haynes T W, Hedetniemi S T, Slater P J. Fundamentals of Domina-
tion in Graphs. New York, USA: Marcel Dekker, 1998
[3] Li J J. Topological Methods on the Theory of Covering Generalized Rough Sets. Pattern Recognition and Artificial Intelligence, 2004, 17(1): 7-10 (in Chinese)
(李进金.覆盖广义粗集理论中的拓扑学方法.模式识别与人工智能, 2004, 17(1): 7-10)
[4] Liu J N K, Hua Y X, He Y L. A Set Covering Based Approach to Find the Reduct of Variable Precision Rough Set. Information Scie-nces, 2014, 275: 83-100
[5] Chen C Y, Li Z G. A Study of Reduction of Attributes and Set Covering Problem. Computer Engineering and Applications, 2004, (2): 44-46, 84 (in Chinese)
(陈彩云,李治国.关于属性约简和集合覆盖问题的探讨.计算机工程与应用, 2004, (2): 44-46, 84)
[6] Chen J K, Li J J. An Application of Rough Sets to Graph Theory. Information Sciences, 2012, 201: 114-127
[7] Lu G, Zhou M T, Tang Y, et al. A Survey on Exact Algorithms for Dominating Set Related Problems in Arbitrary Graphs. Chinese Journal of Computers, 2010, 33(6): 1073-1087 (in Chinese)
(路 纲,周明天,唐 勇,等.任意图支配集精确算法回顾.计算机学报, 2010, 33(6): 1073-1087)
[8] Yu H, Yang D C. Approach to Solving Attribute Reductions with Ant Colony Optimization. Pattern Recognition and Artificial Intelligence, 2011, 24(2): 176-184 (in Chinese)
(于 洪,杨大春.基于蚁群优化的多个属性约简的求解方法.模式识别与人工智能, 2011, 24(2): 176-184)
[9] Liang J Y, Shi Z Z. The Information Entropy, Rough Entropy and Knowledge Granulation in Rough Set Theory. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2004, 12(1): 37-46
[10] Qian Y H, Liang J Y, Pedrycz W, et al. Positive Approximation: An Accelerator for Attribute Reduction in Rough Set Theory. Artificial Intelligence, 2010, 174(9/10): 597-618
[11] Miao D Q, Hu G R. A Heuristic Algorithm for Reduction of Knowledge. Journal of Computer Research & Development, 1999, 36(6): 681-684 (in Chinese)
(苗夺谦,胡桂荣.知识约简的一种启发式算法.计算机研究与发展, 1999, 36(6): 681-684)
[12] Skowron A, Rauszer C. The Discernibility Matrices and Functions in Information Systems // Sowiński R, ed. Intelligent Decision Support. Dordrecht, The Netherlands: Springer, 1992: 331-362
[13] S′lezak D. Approximate Entropy Reducts. Fundamenta Informaticae, 2002, 53(3/4): 365-390
[14] Yao Y Y, Zhao Y. Discernibility Matrix Simplification for Constructing Attribute Reducts. Information Sciences, 2009, 179(7): 867-882
[15] Wang G Y, Yu H, Yang D C. Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers, 2002, 25(7): 759-766 (in Chinese)
(王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7): 759-766) |
|
|
|
2015, Vol. 28 
