Two efficient local search algorithms for the vertex bisection minimization problem

and , where is improved from for large graphs. The main idea in is the bucket sorting technology, which greatly reduces the calculation time of the algorithm to improve the efficiency of the algorithm. Moreover, to improve the performance on large graphs, we propose a top-swap strategy and an information perturbation strategy to improve , resulting in the algorithm. The top-swap strategy is a strategy to maintain the balance between the quality of the new solution and the time required to search for the new solution. The information perturbation strategy is used to help local search escape from local optima and restart the search in a new area. We adopted several sets of popular graph instances to evaluate our algorithms, and the experiments show that the proposed algorithms are significantly better than the current optimal algorithm for most graph instances.