| Summary: | The minimum vertex cover problem is a well-known optimization problem; it has been used in a wide variety of applications. This paper focuses on rough set-based approach for the minimum vertex cover problem of the dynamic and static hypergraphs. First, we demonstrate the relationship between the attribute reduction of decision table and the minimum vertex cover of hypergraph, and the minimum vertex cover problem is converted to an attribute reduction problem based on this relationship. Then, we discuss the update mechanism of minimum vertex cover from the perspective of attribute reduction, and two types of incremental attribute reduction algorithms are proposed, one is the dynamic increase of single vertex and the other is the dynamic increase of multiple vertices. Our algorithms can quickly update the minimum vertex cover in a dynamic hypergraph and improve the rough sets-based method for the minimum vertex cover problem of a static hypergraph in terms of the computational time and the solution quality. The experimental results show the advantages and limitations of the proposed algorithms compared with the existing algorithms.
|
|---|