A rough set method for the minimum vertex cover problem of graphs

The above figure reveals that the new proposed method based on rough sets (VCAR) performs better than the Greedy, List and VSA algorithms on the ratio values for all the graphs listed in the data set. The ratio value is an important index to measure the quality of a solution derived by an algorithm for the minimum vertex cover problem (MVCP), which is defined as Value/Optimum, where Value is the value of a solution found by an algorithm, and Optimum is the optimal solution value. Note that for an approximate algorithm for MVCP, the smaller the ratio value is, the better the algorithm performs. The value found by the VCAR method is quite close to the optimal solution value. We can infer that the new presented algorithm (VCAR) is an effective method for MVCP. 155