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

Research paper by Jinkun Chen, Yaojin Lin, Jinjin Li, Guoping Lin, Zhouming Ma, Anhui Tan

Indexed on: 18 Mar '16Published on: 11 Feb '16Published in: Applied Soft Computing


The minimum vertex cover problem is a classical combinatorial optimization problem. This paper studies this problem based on rough sets. We show that finding the minimal vertex cover of a graph can be translated into finding the attribute reduction of a decision information table. At the same time, finding a minimum vertex cover of graphs is equivalent to finding an optimal reduct of a decision information table. As an application of the theoretical framework, a new algorithm for the minimum vertex cover problem based on rough sets is constructed. Experiments show that the proposed algorithm gets better performance in terms of the ratio value when compared with some other algorithms.

Graphical abstract 10.1016/j.asoc.2016.02.003.jpg
Figure 10.1016/j.asoc.2016.02.003.0.jpg
Figure 10.1016/j.asoc.2016.02.003.1.jpg
Figure 10.1016/j.asoc.2016.02.003.2.jpg