## 3 The Circuit-Partitioning Algorithm Based on Partition Connectivity Clustering and Tabu Search
### Refinement Partitioning Algorithm Based on Tabu Search
#### 3.4.5 Fast Search Method for High-Gain Vertices Based on Bucket Data Structure and Hash Table  
In the circuit-partitioning problem, a vertex \(v\) is considered a \"boundary vertex\" only if it is adjacent to at least one vertex in subset \(G_{i}\). Only boundary vertices may be moved to \(G_{i}\), while moving non-boundary vertices not only has no effect but may also decrease the quality of the partition. Therefore, the algorithm's neighborhood solution-generation strategy focuses only on boundary vertices, avoiding the consideration of all vertices. This not only improves search efficiency but also significantly reduces computational complexity.  
In this paper, we propose a bucket data structure for k-way partitioning. Specifically, the algorithm maintains k bucket arrays, each corresponding to a subset. Each array contains buckets represented by doubly linked lists, where each list holds the gain and the corresponding vertex. A hash table is also used to quickly locate each vertex in the doubly linked list. This structure allows for constant-time transfers of vertices between buckets during gain updates, improving efficiency.  
In the search process, the algorithm only considers boundary vertices and stores them in the bucket data structure. For each vertex \(v\) and its current subset \(G_{c}\), the gain \(g(v,m)\) can be computed in \(O(1)\) time. The vertex \(v\) is only placed in the corresponding bucket if there is a vertex in \(G_{m}\) that is adjacent to \(v\). The gain of the vertices adjacent to \(v\) is also updated in \(O(1)\) time. Therefore, the complexity of moving a vertex from one subset to the target subset depends only on the number of vertices adjacent to \(v\). Analysis shows that \(k\) has little impact on computation time but increases memory requirements.  
Figure 6 shows a schematic diagram of the bucket sorting data structure for a three-way partition of a graph with seven vertices.  
In Figure 6, there are 7 vertices, labeled from 1 to 7, which belong to three distinct subsets: \(G_{1}=\{1,2\}\), \(G_{2}=\{4,6,7\}\), and \(G_{3}=\{3,5\}\). The right side of Figure 6 shows  
Figure 6: Illustration of the three –partition bucket sorting data structure. Seven vertices are grouped into three subsets: \(G_{1}=\{1,2\}\), \(G_{2}=\{4,6,7\}\), and \(G_{3}=\{3,5\}\). The bucket array on the right stores vertices by their gain values, using linked lists for efficient updates. A hash table helps quickly locate each vertex for migration.  
the corresponding bucket array structure. Each bucket array contains multiple linked lists, where each list stores vertices along with their gain information. For example, the bucket array includes buckets with different gain values such as 2, 1, 0, \(-\)1, \(-\)2, \(-\)3, and the corresponding vertices are stored in these buckets. Vertices with the same gain value are linked using a doubly linked list. The hash table facilitates the quick lookup of each vertex's position in the doubly linked list, allowing for efficient vertex migration between buckets when updating the gain values, thereby enhancing the overall execution efficiency of the algorithm.