Algorithm for finding all attribute reduction of a decision - Giang, Nguyễn Long; Thi, Vũ Đức (Journal of Computer Science and Cybernetics, 2012)
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.