Efficient Breadth-First Reduct Search

Veera Boonjing and Pisit Chanvarasuth
Additional contact information
Veera Boonjing: Department of Computer Engineering, Faculty of Engineering, King Mongkut’s Institute of Technology Ladkrabang, Ladkrabang, Bangkok 10520, Thailand
Pisit Chanvarasuth: School of Management Technology, Sirindhorn International Institute of Technology, Thammasat University, Pathum Thani, Bangkok 10200, Thailand

Mathematics, 2020, vol. 8, issue 5, 1-12

Abstract: This paper formulates the problem of determining all reducts of an information system as a graph search problem. The search space is represented in the form of a rooted graph. The proposed algorithm uses a breadth-first search strategy to search for all reducts starting from the graph root. It expands nodes in breadth-first order and uses a pruning rule to decrease the search space. It is mathematically shown that the proposed algorithm is both time and space efficient.

Keywords: reduct; subset; feature selection; breadth-first search; rooted graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/5/833/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/5/833/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:5:p:833-:d:361045

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().