# Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms
## 3 A MVC Solver Based on MEA--Q-MaeMetaVC
### Algorithm Description
//output result
```  
**Algorithm 2**Q-MaeMetaVC/Membrane evolution algorithm for solving the MVCP  
```
Input: graph G = (V, E), number of groups \(N\), longest running time \(MRT\), number of divisions and fusions in a single iteration iterCount, the number of side extractions \(bms\_e\), the number of vertex extractions \(bms\_v\), the maximum cytolysis \(maxReC\)Custruct; Output: a coverage of graph G; (1) Preprocessing: Simplify the scale of the graph 1 <G' = (V', E), Info> = PreP(G);//Refer to the PreP algorithm in [13] 2 Create an empty Answer membrane in the P membrane; 3 \(p\overset{Info}{\rightarrow}\) Answer; //Initialize the membrane structure 4 if G' is a connected component of a bipartite graph, then 5 CBP = ConstructMembranel; // Constructing the initial membrane structure of bipartite graphs. Refer to Algorithm 3 6 else CP = ConstructMembranel; // Constructing the initial membrane structure of the non-bipartite graph. Refer to Algorithm 5 (2) Bipartite graph solution stage for CB\({}_{i}\) in CBP do://Can be parallelized; the actual implementation is serial processing 8 CB\({}_{j}\)best = Bipartite_graph(G(V\({}_{j}\)));//Refer to Algorithm 4 Answer+ CB\({}_{j}\)best; 10 Cytolysis (CB\({}_{j}\)) (3) Non-bipartite graph solution stage //Organize the information 11 if (C\({}_{i}\) membrane exists) then 12 \(vNumLeft\) = the sum of the number of objects of the C\({}_{i}\) membrane; //Q-Meta search process 13 for C\({}_{i}\) in CP do //can be parallelized; the actual implementation is serial processing 14 \(MRT_{i}\) = \(MRT_{i}\)/\(vNumLeft\)* \(|V_{i}|\); 15 C\({}_{i}\) = ConstructMetaPopulations(\(i\), 3*N); //refer to Algorithm 6 repairPopulation(C\({}_{i}\), MP); //refer to Algorithm 7 Repeat (a) Division and fusion //parallel 18 Division_and_Fusion(C\({}_{i}\),MP, iterCount, bms_k, bms_e); (b) Synchronous information retrieval end condition //serial 19 bestMem = the membrane with the smallest number of elements in C\({}_{i}\)best (when the number of elements is the same, choose the membrane with the shortest time and the fewest search steps); 20 if(\(|\)bestMem \(|<|\)C\({}_{i}\),best\(|\)) C\({}_{i}\)best = bestMem; //determine whether to terminate 21 if(running time> = \(MRT_{i}\)) then: 22 Answer + C\({}_{i}\),best; 23 Cytolysis(C\({}_{i}\)); 24 break; 25 repairPopulation(C\({}_{i}\),MP); //refer to Algorithm 7 (c) selection and Cytolysis //parallel 26 CytolysisAndSelection(C\({}_{i}\),MP, maxReCustruct); 27 until false; (4) Inverse processing stage Inv_PreP(Answer); //refer to the Inv_PreP algorithm in [13] return Answer. //output result
```  
**Algorithm 3**Q-MaeMetaVC/Membrane evolution algorithm for solving the MVCP  
Non-bipartite graph solution stage. It mainly includes information organization and the Q-Meta process. 1 Organize information. If C\({}_{i}\) membranes exist, count the total number of objects in the C (lines 11-12), and solve the vertex cover it is responsible for in the Q-Meta stage; otherwise, enter the inverse processing stage. 2 Q-Meta process. Each C\({}_{i}\) membrane will solve the vertex cover of the corresponding connected component. Q-MaeMetaVC allocates the running time of each C\({}_{i}\) proportional to the number of vertices of the connected component (line 14). Before searching, use the ConstructMetaPopulation algorithm (Algorithm 6) for C\({}_{i}\) to construct MP, GOODP and initialize its best membrane (line 15). After that, Q-MeaMetaVC will use the repair operator (line 16, Section 3.4.2), division and fusion operator (line 18, Section 3.4.3), and the selection and cytolysis operator (line 26, Section 3.4.4) to try to find better vertex cover of G(V\({}_{i}\)) until reaching the end condition. The Answer membrane will fuse with the C\({}_{i}\).best membrane (line 22), and then the C\({}_{i}\) will lyse itself (line 23). When all C\({}_{i}\) is dissolved, it will enter the reverse processing stage. 1.