## 3 The Circuit-Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search
### Initial Partitioning Algorithm Based on Partition Connectivity Clustering  
The coarsened graph \(G_{m}\) was generated using Algorithm 1 in the previous section. The next step is to perform the initial partitioning. In detail, the vertices of the graph \(G_{m}\) are assigned to \(k\) subsets \(G_{i}\) (\(G_{i}\in\{G_{1}(V_{1},E_{1}),G_{2}(V_{2},E_{2}),\ldots,G_{k}(V_{k},E_{k})\}\)), ensuring that the number of vertices in each subset is as balanced as possible. Figure 4: Illustration of an example of the coarsening algorithm based on edge-priority matching. The graph on the left shows eight vertices connected by weighted edges. The table on the right displays the matching status for each vertex pair. The matched vertex pairs are (1,8), (2,3), (4,6), and (5,7), with a total of 17 edges in the coarsened graph. We propose an initial partitioning algorithm based on partition connectivity clustering to minimize the number of cut edges, and the main process of this algorithm is shown in Algorithm 2. ```
1:Input: Input graph structure \(G_{m}\), number of subsets \(k\), minimum cluster weight limit \(LR\)
2:Output: Subgraph set \(S\)
3:Variable: Selected vertex \(v_{r}\), a subgraph \(G_{i}\), graph \(G^{\prime}\)
4:\(G^{\prime}=G_{m}\)
5:\(S=\{\}\)
6:for\(i=1\) to \(k\)do
7:\(v_{r}=\text{random select}(G^{\prime})\)
8:\(G_{i}=\text{ClusterSearch}(v_{r},LR,G^{\prime})\)
9:\(\text{S\_append}(G_{i})\)
10:\(G^{\prime}=G^{\prime}-G_{i}\)
11:endfor
12:return\(S\)
```  
**Algorithm 2** Initial Partitioning Algorithm Based on Partition Connectivity Clustering  
For each subset \(G_{i}(V_{i},E_{i})\), first, a vertex \(v_{r}\) is randomly selected as the starting point. In the subsequent steps, as described in the ClusterSearch algorithm (Algorithm 3), the partition connectivity degree in \(G_{m}\) connected to the \(G_{i}(V_{i},E_{i})\) is calculated. The vertex with the highest connectivity degree is then added to \(G_{i}\). This process is iterated repeatedly until the weight of \(G_{i}\) exceeds the threshold \(LR\), and the ClusterSearch function returns \(G_{i}\). Finally, \(G_{m}\) is corrected by removing \(G_{i}\) from it, and clustering for the next partition begins. ```
1:Input: The corrected graph structure \(G^{\prime}\), the minimum limit of cluster weight \(LR\), and the initial vertex \(v_{r}\)
2:Output: The current subgraph \(G_{i}(V_{i},E_{i})\)
3:Variable: The candidate vertices set \(sel_{v\_{c}and}\)
4:\(G_{i}\).add\((v_{r})\)
5:while\(G_{i}\).weight\(<LR\)and\(sel_{v\_{c}and}\
eq\emptyset\)do
6:\(set_{v\_{c}and}(vertices\_{c}\_{c}\_{c}\_{c}(G_{i}))\)
7:forach vertex \(v\in set_{v\_{c}and}\):
8:\(C(v,i)=\text{count\_edges}(v,G_{i})\)
9:\(v_{next}=\text{argmax}(connectivity)\)
10:\(G_{i}\).add\((v_{next})\)
11:\(set_{v\_{c}and}\).remove\((v_{next})\)
12:endwhile
13:return\(G_{i}(V_{i},E_{i})\)
```  
**Algorithm 3** ClusterSearch Algorithm  
Figure 5 illustrates an example of Algorithm 3. Assuming vertex 2 is chosen as the initial vertex and is assigned to the starting partition \(G_{1}=\{v_{2}\}\), then the adjacent vertices 1, 3, and 4 are considered as candidate vertices. Next, the partition connectivity of each candidate vertex, including \(C(v_{1},G_{1})\), \(C(v_{3},G_{1})\), and \(C(v_{4},G_{1})\), is calculated as 1, 2, and 1, respectively. Therefore, vertex 3 is selected and added into the first partition; it has \(G_{1}=\{v_{2},v_{3}\}\). In Figure 5, the total partition connectivity between vertex 1 and \(G_{1}\) is 3. Similarly, it has \(C(v_{5},G_{1})=3\), \(C(v_{4},G_{1})=3\). These adjacent vertices have the same partition connectivity, so the number of edge cuts is considered. In detail, clustering vertex 1 results in 7 edge cuts, clustering vertex 5 results in 9 edge cuts, and clustering vertex 4 results in 13 edge cuts. To minimize edge cuts, vertex 1 is selected and \(G_{1}=\{v_{1},v_{2},v_{3}\}\). In Figure 5c, the total partition connectivity between vertex 5 and \(G_{1}\) is 4, while the total partition connectivity of vertex 4 is 3. Therefore, vertex 5 is selected.