Photo from wikipedia
Minimal vertex cover problem (MVCP) is a famous important NP-hard problem in graph theory. It has been reported that MVCP is equivalent to finding reducts of information systems in rough… Click to show full abstract
Minimal vertex cover problem (MVCP) is a famous important NP-hard problem in graph theory. It has been reported that MVCP is equivalent to finding reducts of information systems in rough sets theory. This relationship motivates our idea to deal with MVCP in terms of approaches to discernibility matrix in rough set. First we point out that only minimal elements in the discernibility matrix are useful for MVCP, and we present a novel algorithm based on minimal elements for MVCP. Then we make experimental comparisons to demonstrate the effectiveness of this new algorithm on big graphs.
Journal Title: International Journal of Machine Learning and Cybernetics
Year Published: 2019
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!