## 3 The Circuit-Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search
### Refinement Partitioning Algorithm Based on Tabu Search  
Using Algorithms 2 and 3, an initial solution is obtained. The uncoarsening process is just the inverse process of the coarsening phase. Subsequently, in the refinement phase, a tabu search algorithm is employed to optimize the number of cut edges while maintaining load balancing. Tabu search works by continuously replacing the current solution with the best neighborhood solution that has not been recently visited, thereby exploring a broader search space. The core of tabu search combines intelligent search with learning principles. It uses a flexible memory mechanism to record and leverage search history, avoiding redundant searches and improving both search efficiency and solution quality. Building on this, we propose an effective neighborhood search strategy that explores a broader solution space through reasonable neighborhood selection to improve search quality and efficiency. We also present a perturbation method to improve its global search ability, increase the likelihood of escaping local optima, and enhance the flexibility and effectiveness of the search process. Figure 5: Example of the clustering process based on cluster connectivity priority. The red vertices represent the selected vertices, while the blue vertices represent the candidate vertices. (**a**) Vertex 3 is selected for \(G_{1}=\{v_{2},v_{3}\}\). (**b**) Vertex 1 is added to \(G_{1}=\{v_{1},v_{2},v_{3}\}\) after considering edge cuts. (**c**) Vertex 5 is added to \(G_{1}\). (**d**) Clustering stops when the threshold is exceeded. Algorithm 4 shows the refinement process. The initial solution, current solution, candidate solution, and best solution are denoted as \(P_{\text{Ginit}}^{k}\), \(P_{\text{Gcurr}}^{k}\), \(P_{\text{Grand}}^{k}\), and \(P_{\text{Gbest}}^{k}\), respectively. The initial solution \(P_{\text{Ginit}}^{k}\) is generated by the initial partitioning algorithm based on partition connectivity clustering, and its neighborhood solutions are obtained by adjusting adjacent vertices. In detail, Algorithm 4 defines two neighborhood solution-generation rules, R1 and R2, aimed at optimizing the objective (i.e., reducing cut edges) and maintaining load balancing by moving vertices in the current solution. Typically, these rules move vertices from subsets with higher weights to subsets with lower weights. Through these directed movements, the search process gradually adjusts the load balancing, bringing it closer to the ideal state. In the candidate solution-selection process, the frequency of vertex movement is applied to avoid frequently adjusting the same vertex and improve the calculation efficiency. It is noted that the new solution will only be updated as the best solution if it is at least as good as the current solution (k-partition) in terms of both the optimization objective and load balancing. Additionally, a perturbation method is suggested: if the optimal solution is not updated after \(\gamma\) iterations, the current solution is perturbed to increase the possibility of escaping local optima. ```
1:Input: The input graph \(G_{i}\), initial partition \(P_{\text{Ginit}}^{k}\)
2:Output: Best partition \(P_{\text{Ginit}}^{k}\)
3:Variable: Init partition \(P_{\text{Ginit}}^{k}\), current partition \(P_{\text{Gcurr}}^{k}\), candidate partition \(P_{\text{Grand}}^{k}\), Candidate vertex set \(V_{\text{Grand}}\)
4: Initialize iteration count, tabu list, vertex movement frequency table, and tabu tenure. 5:\(P_{\text{Gbest}}^{k}=P_{\text{Ginit}}^{k}\)
6:for each vertex \(v\) and each subset \(G_{m}\)do
7: Compute move gain \(g(v,m)\) by Formula (7)
8: Place \(v\) into the bucket structure associated with \(G_{m}\)
9:endfor
10:repeat
11: // Neighborhood Solution Generation Strategy
12: Loop through the two neighborhood generation rules \(R1\) and \(R2\). 13:if turn to \(R1\)then
14: // Move a single vertex operation
15: Select \(S_{m}\) and vertex \(v_{m}\) for migration
16: Add candidate solution vertices to \(V_{cand}\) according to rule \(R1\).