Double Check and Balance Competition Algorithm for Vertex-Weighted Connected Subgraph Partition Problem

The balanced <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> partition problem for weighted graphs is to divide the vertices or edges of the graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex> into <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> disjoint subsets, so that the weights among the subsets are as balanced as possible, and the constraints are different for different application scenarios. For example, when the vertex weight balance of the subset is satisfied, the edge weight must be as small as possible, the induced subgraph generated by the subset must be connected, or the edge weight of the minimum spanning tree of the induced subgraph must be balanced. This paper to solve the problem that the subgraph must be connected after the balanced <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> partition of the undirected connected graph G with vertex weights, a heuristic double balance algorithm is proposed which can generate good solutions. Firstly, the double balancing strategy of “Sequential Incremental” and “Offsetting Deficiencies by Reducing Surpluses” are designed to ensure the superiority of the initial division and the rapidity of the subsequent evolution. The feasibility of the double balancing strategy is proved based on mathematical method. Then, the optimal result is selected by the rules of the competition based on the dual balance strategy. Finally, the effectiveness and operability of the algorithm are verified by a concrete case, which has certain reference significance for solving and optimizing related problems.