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, 1-7

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: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/JAM/2013/519173.pdf (application/pdf)
http://downloads.hindawi.com/journals/JAM/2013/519173.xml (text/xml)

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:hin:jnljam:519173

DOI: 10.1155/2013/519173

Access Statistics for this article

More articles in Journal of Applied Mathematics from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().