Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets
Joint Authors
Zhu, William
Wang, Shiping
Zhu, Qingxin
Min, Fan
Source
Journal of Applied Mathematics
Issue
Vol. 2013, Issue 2013 (31 Dec. 2013), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2013-05-22
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Wang, Shiping& Zhu, Qingxin& Zhu, William& Min, Fan. 2013. Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets. Journal of Applied Mathematics،Vol. 2013, no. 2013, pp.1-7.
https://search.emarefa.net/detail/BIM-478135
Modern Language Association (MLA)
Wang, Shiping…[et al.]. Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets. Journal of Applied Mathematics No. 2013 (2013), pp.1-7.
https://search.emarefa.net/detail/BIM-478135
American Medical Association (AMA)
Wang, Shiping& Zhu, Qingxin& Zhu, William& Min, Fan. Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets. Journal of Applied Mathematics. 2013. Vol. 2013, no. 2013, pp.1-7.
https://search.emarefa.net/detail/BIM-478135
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-478135