Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough Sets
The minimum vertex cover problem is a well-known optimization problem; it has been used in a wide variety of applications. This paper focuses on rough set-based approach for the minimum vertex cover problem of the dynamic and static hypergraphs. First, we demonstrate the relationship between the att...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2018-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8454706/ |
| _version_ | 1818871937707802624 |
|---|---|
| author | Qian Zhou Xiaolin Qin Xiaojun Xie |
| author_facet | Qian Zhou Xiaolin Qin Xiaojun Xie |
| author_sort | Qian Zhou |
| collection | DOAJ |
| description | The minimum vertex cover problem is a well-known optimization problem; it has been used in a wide variety of applications. This paper focuses on rough set-based approach for the minimum vertex cover problem of the dynamic and static hypergraphs. First, we demonstrate the relationship between the attribute reduction of decision table and the minimum vertex cover of hypergraph, and the minimum vertex cover problem is converted to an attribute reduction problem based on this relationship. Then, we discuss the update mechanism of minimum vertex cover from the perspective of attribute reduction, and two types of incremental attribute reduction algorithms are proposed, one is the dynamic increase of single vertex and the other is the dynamic increase of multiple vertices. Our algorithms can quickly update the minimum vertex cover in a dynamic hypergraph and improve the rough sets-based method for the minimum vertex cover problem of a static hypergraph in terms of the computational time and the solution quality. The experimental results show the advantages and limitations of the proposed algorithms compared with the existing algorithms. |
| first_indexed | 2024-12-19T12:30:51Z |
| format | Article |
| id | doaj.art-d6e974b058c14e2692d990670e4e1879 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-19T12:30:51Z |
| publishDate | 2018-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-d6e974b058c14e2692d990670e4e18792022-12-21T20:21:24ZengIEEEIEEE Access2169-35362018-01-016501425015310.1109/ACCESS.2018.28688468454706Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough SetsQian Zhou0https://orcid.org/0000-0001-7888-2419Xiaolin Qin1https://orcid.org/0000-0002-8845-1089Xiaojun Xie2https://orcid.org/0000-0002-4848-1099College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, ChinaCollege of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, ChinaCollege of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, ChinaThe minimum vertex cover problem is a well-known optimization problem; it has been used in a wide variety of applications. This paper focuses on rough set-based approach for the minimum vertex cover problem of the dynamic and static hypergraphs. First, we demonstrate the relationship between the attribute reduction of decision table and the minimum vertex cover of hypergraph, and the minimum vertex cover problem is converted to an attribute reduction problem based on this relationship. Then, we discuss the update mechanism of minimum vertex cover from the perspective of attribute reduction, and two types of incremental attribute reduction algorithms are proposed, one is the dynamic increase of single vertex and the other is the dynamic increase of multiple vertices. Our algorithms can quickly update the minimum vertex cover in a dynamic hypergraph and improve the rough sets-based method for the minimum vertex cover problem of a static hypergraph in terms of the computational time and the solution quality. The experimental results show the advantages and limitations of the proposed algorithms compared with the existing algorithms.https://ieeexplore.ieee.org/document/8454706/Vertex coverattribute reductionrough setshypergraph |
| spellingShingle | Qian Zhou Xiaolin Qin Xiaojun Xie Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough Sets IEEE Access Vertex cover attribute reduction rough sets hypergraph |
| title | Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough Sets |
| title_full | Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough Sets |
| title_fullStr | Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough Sets |
| title_full_unstemmed | Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough Sets |
| title_short | Dimension Incremental Feature Selection Approach for Vertex Cover of Hypergraph Using Rough Sets |
| title_sort | dimension incremental feature selection approach for vertex cover of hypergraph using rough sets |
| topic | Vertex cover attribute reduction rough sets hypergraph |
| url | https://ieeexplore.ieee.org/document/8454706/ |
| work_keys_str_mv | AT qianzhou dimensionincrementalfeatureselectionapproachforvertexcoverofhypergraphusingroughsets AT xiaolinqin dimensionincrementalfeatureselectionapproachforvertexcoverofhypergraphusingroughsets AT xiaojunxie dimensionincrementalfeatureselectionapproachforvertexcoverofhypergraphusingroughsets |