Algorithm for finding all attribute reduction of a decision

Nguyễn Long Giang, Vũ Đức Thi


Attribute reduction is one of the most important issues in rough set theory. There are many scientific papers that suppose algorithms on attribute reduction algorithms. However, they are all heuristic algorithms that find the best attribute reduction based on a kind of heuristic information. In this paper, we present a new algorithm for finding all attribute reductions of a decision and we show that the time complexity of the algorithm is exponential in the number of attributes. We also show that this complexity is polynomial in many special cases.

DOI: Display counter: Abstract : 183 views. PDF : 93 views. PDF (Tiếng Việt) : 19 views.


Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology