Equivalent Characterizations of Some Graph Problems by Covering‐Based Rough Sets

Shiping Wang, Qingxin Zhu, William Zhu and Fan Min

Journal of Applied Mathematics, 2013, vol. 2013, issue 1

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

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2013/519173

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2013:y:2013:i:1:n:519173

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().