Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms
In recent years, the rapid development of the internet and the advancement of information technology have produced a large amount of large-scale data, some of which are presented in the form of large-scale graphs, such as social networks and sensor networks. Minimum vertex cover (MVC) is an importan...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-07-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/13/14/8021 |
| _version_ | 1797590458391592960 |
|---|---|
| author | Chunmei Liao Ping Guo Jiaqi Gu Qiuju Deng |
| author_facet | Chunmei Liao Ping Guo Jiaqi Gu Qiuju Deng |
| author_sort | Chunmei Liao |
| collection | DOAJ |
| description | In recent years, the rapid development of the internet and the advancement of information technology have produced a large amount of large-scale data, some of which are presented in the form of large-scale graphs, such as social networks and sensor networks. Minimum vertex cover (MVC) is an important problem in large-scale graph research. This paper proposes a solver Q-MeaMetaVC based on the MVC framework PEAF and the membrane evolution algorithm framework MEAF. First, the graph is reduced and divided into two types of connected components (bipartite graph and non-bipartite graph) to reduce the scale of the problem. Second, different membrane structures are designed for different types of connected components to better represent the connected component features and facilitate solutions. Third, a membrane evolution algorithm (MEA), which includes fusion, division, cytolysis, and selection operators, is designed to solve the connected components. Then, Q-MeaMetaVC is compared with the best MVC solver in recent years on the test set, and good experimental results that are obtained verify the feasibility and effectiveness of Q-MeaMetaVC in solving the MVC of large-scale graphs. |
| first_indexed | 2024-03-11T01:21:44Z |
| format | Article |
| id | doaj.art-8d7d4c4d798f4f708c15a6e9d50613c4 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-11T01:21:44Z |
| publishDate | 2023-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-8d7d4c4d798f4f708c15a6e9d50613c42023-11-18T18:07:03ZengMDPI AGApplied Sciences2076-34172023-07-011314802110.3390/app13148021Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary AlgorithmsChunmei Liao0Ping Guo1Jiaqi Gu2Qiuju Deng3School of Big Data and Computer Science Engineering, Chongqing College of Mobile Communication, Chongqing 401520, ChinaCollege of Computer Science, Chongqing University, Chongqing 400044, ChinaCollege of Computer Science, Chongqing University, Chongqing 400044, ChinaSchool of Big Data and Computer Science Engineering, Chongqing College of Mobile Communication, Chongqing 401520, ChinaIn recent years, the rapid development of the internet and the advancement of information technology have produced a large amount of large-scale data, some of which are presented in the form of large-scale graphs, such as social networks and sensor networks. Minimum vertex cover (MVC) is an important problem in large-scale graph research. This paper proposes a solver Q-MeaMetaVC based on the MVC framework PEAF and the membrane evolution algorithm framework MEAF. First, the graph is reduced and divided into two types of connected components (bipartite graph and non-bipartite graph) to reduce the scale of the problem. Second, different membrane structures are designed for different types of connected components to better represent the connected component features and facilitate solutions. Third, a membrane evolution algorithm (MEA), which includes fusion, division, cytolysis, and selection operators, is designed to solve the connected components. Then, Q-MeaMetaVC is compared with the best MVC solver in recent years on the test set, and good experimental results that are obtained verify the feasibility and effectiveness of Q-MeaMetaVC in solving the MVC of large-scale graphs.https://www.mdpi.com/2076-3417/13/14/8021membrane evolutionary algorithmminimum vertex coverlarge-scale graphsmembrane computing |
| spellingShingle | Chunmei Liao Ping Guo Jiaqi Gu Qiuju Deng Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms Applied Sciences membrane evolutionary algorithm minimum vertex cover large-scale graphs membrane computing |
| title | Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms |
| title_full | Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms |
| title_fullStr | Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms |
| title_full_unstemmed | Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms |
| title_short | Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms |
| title_sort | q meametavc an mvc solver of a large scale graph based on membrane evolutionary algorithms |
| topic | membrane evolutionary algorithm minimum vertex cover large-scale graphs membrane computing |
| url | https://www.mdpi.com/2076-3417/13/14/8021 |
| work_keys_str_mv | AT chunmeiliao qmeametavcanmvcsolverofalargescalegraphbasedonmembraneevolutionaryalgorithms AT pingguo qmeametavcanmvcsolverofalargescalegraphbasedonmembraneevolutionaryalgorithms AT jiaqigu qmeametavcanmvcsolverofalargescalegraphbasedonmembraneevolutionaryalgorithms AT qiujudeng qmeametavcanmvcsolverofalargescalegraphbasedonmembraneevolutionaryalgorithms |