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 se...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2013/519173 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832550755121233920 |
|---|---|
| author | Shiping Wang Qingxin Zhu William Zhu Fan Min |
| author_facet | Shiping Wang Qingxin Zhu William Zhu Fan Min |
| author_sort | Shiping Wang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-52d824c8c81c4a4d9d7b64b762ee9e8d |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-52d824c8c81c4a4d9d7b64b762ee9e8d2025-02-03T06:05:57ZengWileyJournal of Applied Mathematics1110-757X1687-00422013-01-01201310.1155/2013/519173519173Equivalent Characterizations of Some Graph Problems by Covering-Based Rough SetsShiping Wang0Qingxin Zhu1William Zhu2Fan Min3School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, ChinaSchool of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, ChinaLab of Granular Computing, Minnan Normal University, Zhangzhou, Fujian 363000, ChinaLab of Granular Computing, Minnan Normal University, Zhangzhou, Fujian 363000, ChinaCovering 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.http://dx.doi.org/10.1155/2013/519173 |
| spellingShingle | Shiping Wang Qingxin Zhu William Zhu Fan Min Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets Journal of Applied Mathematics |
| title | Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets |
| title_full | Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets |
| title_fullStr | Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets |
| title_full_unstemmed | Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets |
| title_short | Equivalent Characterizations of Some Graph Problems by Covering-Based Rough Sets |
| title_sort | equivalent characterizations of some graph problems by covering based rough sets |
| url | http://dx.doi.org/10.1155/2013/519173 |
| work_keys_str_mv | AT shipingwang equivalentcharacterizationsofsomegraphproblemsbycoveringbasedroughsets AT qingxinzhu equivalentcharacterizationsofsomegraphproblemsbycoveringbasedroughsets AT williamzhu equivalentcharacterizationsofsomegraphproblemsbycoveringbasedroughsets AT fanmin equivalentcharacterizationsofsomegraphproblemsbycoveringbasedroughsets |