# Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms
## 3 A MVC Solver Based on MEA--Q-MaeMetaVC
### Bipartite Graph Solving Algorithm
#### 3.3.1 Create a Membrane Structure  
The bipartite graph creates a membrane structure, as shown in Algorithm 3. First, create an empty CB\({}_{1}\) membrane in the P membrane, then construct the X, Y, best, and MaxM membranes in the CB\({}_{1}\) membrane. If there are s connected components of the bipartite graph, copy s-1 CB\({}_{1}\) membranes, and finally return to the CBP membrane. ```
Input: s Output: CBP membrane;
1 Create an empty CB\({}_{1}\) membrane in the P membrane;
2 Create an X membrane in the CB1 membrane;
3 Create a Y membrane in the CB1 membrane;
4 Create the best membrane in the CB1 membrane;
5 Create a MaxM membrane in the CB1 membrane; // If there are s bipartite graph-connected components
6 k\(\leftarrow\)2;
7 while k \(\leq\) s do
8 CBP = CB1 U CopyCBtoCB(CB1, CBk); //copy s-1 CB1
9 k\(\leftarrow\)+;
10 end while
11 return CBP membrane;

#### 3.3.2 Algorithm Design

The Bipartite_graph algorithm solves the MVC for each bipartite graph-connected component, as shown in Algorithm 4. First, divide V\({}_{j}\) into two independent sets, X and Y, and put them into the corresponding CB\({}_{j}\).X and CB\({}_{j}\).Y membranes, respectively (lines 1-3). Then, use the _Hungarian_ algorithm [29] to find a maximum matching of G(V\({}_{j}\)), put the matching vertices into the membrane MaxM (line 4), and record the maximum matching number _max_ (line 5). At the same time, the CB\({}_{j}\).X\({}^{\prime}\) and CB\({}_{j}\).Y\({}^{\prime}\) membranes are initialized with unmatched vertices (lines 6-7). If the CB\({}_{j}\).X\({}^{\prime}\) and CB\({}_{j}\).Y\({}^{\prime}\) membranes are both empty, dissolve the CB\({}_{j}\).X\({}^{\prime}\) and CB\({}_{j}\).Y\({}^{\prime}\) membranes and transfer the objects of the CB\({}_{j}\).X or CB\({}_{j}\).Y membranes to the CB\({}_{j}\).best membrane (lines 8-11). If only one of the CB\({}_{j}\).X\({}^{\prime}\) and CB\({}_{j}\).Y\({}^{\prime}\) membranes is empty, dissolve only one (lines 13-16). Transfer the unmatched neighboring vertices to the CB\({}_{j}\).best membrane. If \(\mid\) CB\({}_{j}\).best \(\mid\) equals _max_ and an MVC has been found, end the process. Otherwise, all vertex neighborhoods from the previous step are considered unmatched vertexes, in which case update the X\({}^{\prime}\) and Y\({}^{\prime}\) membranes (Lines 17-25). Finally, return the CB\({}_{j}\).best membrane, which is the MVC of the bipartite graph. ```
Input: G(V\({}_{j}\)) //Each connected bipartite diagram Output: CB\({}_{j}\).best;
1 Put G(V\({}_{j}\)) into the CB\({}_{j}\) membrane; //Divide V\({}_{j}\) into two independent sets, X and Y, and put them into the corresponding X and Y membrane, respectively. 2 CB\({}_{j}\).X\({}^{\leftarrow}\)-an independent set of V\({}_{j}\) in CB\({}_{j}\);
3 CB\({}_{j}\).Y\({}^{\leftarrow}\)-all vertex objects in CB\({}_{j}\);
4 MaxM\(\leftarrow\)Hungarian(G(V\({}_{j}\)));
5 max = 1 MaxM1/2;
6 CB\({}_{j}\).X\({}^{\leftarrow}\)-CB\({}_{j}\).X-MaxM;
7 CB\({}_{j}\).Y\({}^{\leftarrow}\)-CB\({}_{j}\).Y-MaxM;
8 if (CB\({}_{j}\).X\({}^{\prime}\) is empty &&CB\({}_{j}\).Y\({}^{\prime}\) is empty) then
9 Cytolysis(CB\({}_{j}\).X\({}^{\prime}\));
10 Cytolysis(CB\({}_{j}\).Y\({}^{\prime}\));
11 CB\({}_{j}\).best+CB\({}_{j}\).X;
12 else
13 if(CB\({}_{j}\).X\({}^{\prime}\) is empty) then
14 Cytolysis(CB\({}_{j}\).X\({}^{\prime}\));
15 if(CB\({}_{j}\).Y\({}^{\prime}\) is empty) then
16 Cytolysis(CB\({}_{j}\).Y\({}^{\prime}\));
17 n\(\leftarrow\)0;
18 for n < max do
19 CB\({}_{j}\).best\(\leftarrow\)N(CB\({}_{j}\).X\({}^{\prime}\)) U N(CB\({}_{j}\).Y\({}^{\prime}\));
20 if(!CB\({}_{j}\).best \(\mid\) == max) break;
21 else
22 CB\({}_{j}\).X\({}^{\leftarrow}\)N(N(CB\({}_{j}\).X\({}^{\prime}\)));
23 CB\({}_{j}\).Y\({}^{\leftarrow}\)N(N(CB\({}_{j}\).Y\({}^{\prime}\)));
24 n++;
25 end for
26 return CB\({}_{j}\).best membrane;
```
**Algorithm 4**Bipartite_graph(G(V\({}_{j}\))) //Bipartite graph solves MVC

#### 3.3.3 Example Analysis

This section will use Figure 7 as an example to explain the solution process of the Bipartite_graph algorithm.