Equivalent characterizations of some graph problems by covering-based rough sets

Covering is a widely used form of data structures. covering-based rough set theory provides a systematic approach to this data. in this paper,graphs are connected with covering-based rough sets. specifically,we convert some important concepts in graph theory including vertex covers,independent sets,edge covers,and matchings to ones in covering-based rough sets. at the same time,corresponding problems in graphs are also transformed into ones in covering-based rough sets. for example,finding a minimal edge cover of a graph is translated into finding a minimal general reduct of a covering. the main contributions of this paper are threefold. first,any graph is converted to a covering. two graphs induce the same covering if and only if they are isomorphic. second,some new concepts are defined in covering-based rough sets to correspond with ones in graph theory. the upper approximation number is essential to describe these concepts. finally,from a new viewpoint of covering-based rough sets,the general reduct is defined,and its equivalent characterization for the edge cover is presented. these results show the potential for the connection between covering-based rough sets and graphs. © 2013 shiping wang et al.