## 3 The Circuit-Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search
### Coarsening Algorithm Based on Edge-Priority Matching  
The coarsening techniques are widely used as a key step to simplify the original circuit graph and improve the efficiency of subsequent processing. The core operation of the coarsening process is merging two vertices into one. And the random matching or maximum weight matching methods are always used to select the merged vertices. The random matching method matches two adjacent vertices randomly, while the maximum weight matching method matches adjacent vertices with the highest edge weights to effectively reduce the number of cut edges. Figure 3 illustrates the process of maximum weight matching. The original graph consists of eight vertices, and vertices are traversed to select the pair with the highest edge weight from adjacent vertices. The matched vertex pairs are represented by the same color. After merging the matched vertices, a coarsened graph with 20 edges is generated. The maximum weight-matching algorithm traverses vertices sequentially during the matching process, which may overlook some vertices connected by edges with higher weights. For example, in Figure 3, the edge between vertex 5 and vertex 7 has a weight of 5, which is the highest in the original graph, yet it is not matched. To address this issue, a coarsening algorithm based on edge-priority matching is proposed, as shown in Algorithm 1. Figure 2: Transformation from a circuit graph to an adjacency matrix and compressed sparse row (CSR) matrix. The left shows the circuit graph with nodes, the middle shows the adjacency matrix, and the right shows the CSR format with xadj, adjncy, and adjwgt. ```
1:Input: Graph \(G_{1}(V_{1},E_{1})\) with edge weights \(W\), threshold \(V_{limit}\)
2:Output: Coarsened graph \(G_{m}(V_{m},E_{m})\)
3:Variable: Current graph \(G^{\prime}(V^{\prime},E^{\prime})\), unmatched set \(U\), matching set \(M\) (matched vertex pairs)
4:\(G^{\prime}=G_{1}\)
5:while\(|V^{\prime}|>V_{limit}\)do
6: sort edges of \(G^{\prime}\) by weight (descending)
7:\(M\leftarrow\emptyset\)
8:\(U\gets V^{\prime}\)
9:fore each edge \((u,v)\) in sorted edges do
10:if\(u\in U\)and\(v\in U\)then
11:\(M.\text{add}((u,v))\)
12:// Remove these vertices from the unmatched set \(U\)
13:\(U.\text{remove}(u)\)
14:\(U.\text{remove}(v)\)
15:endif
16:endfor
17:Merge vertex weights by Formula (1)
18:// Update edge weight between merged vertices and others
19:\(w(e(v_{(i,j)},v_{k}))=w(e(v_{i},v_{k}))+w(e(v_{j},v_{k}))\)// Formula (2)
20:// Reduce the graph size by halving the number of vertices
21:\(n^{\prime}=\text{floor}\big{(}\frac{n}{2}\big{)}\)// Formula (3)
22:Generate the new subgraph \(G^{\prime}\) based on matched vertices and updated edge weights
23:endwhile
24:return\(G_{m}(V_{m},E_{m})\)
```  
**Algorithm 1** Coarsening Algorithm Based on Edge-Priority Matching  
Algorithm 1 sorts the edges of the current graph in descending order by weight. Next, it iterates through the sorted edges, attempting to match each pair of connected vertices (\(u\), \(v\)). If both vertices are unmatched, they are added to the matching set \(M\) and removed from  
Figure 3: Illustration of the maximum weight-matching process based on vertex traversal. 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,5), and (6,7), with a total of 20 edges in the coarsened graph. \(U\) to mark them as matched. After processing all edges, it generates a new coarsened graph \(G^{\prime}\) using the matched set \(M\), and updates the vertex and edge sets of the graph accordingly. This process repeats until the number of vertices in the graph is less than or equal to \(V_{\text{limit}}\). Finally, it returns the coarsened graph \(G_{m}\). An example is shown in Figure 4. The edges are first sorted by weights. Then, the vertices corresponding to the maximum weight edge, vertices 5 and 7, are matched.