An Efficient Algorithm For Minimal Vertex Covering Problem On Large-Scale Graphs

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...