Research On Graph Partitioning Algorithms With Paths

In recent years,graph partitioning and hypergraph partitioning have been widely used in distributed graph computing,very large scale integrated circuit design and other fields.Scholars have also conducted a lot of research on large-scale graph partitioning algorithms and hypergraph partitioning algorithms.With the continuous development of technology,simply modeling practical problems as graph partitioning problems or hypergraph partitioning problems gradually cannot meet the needs of practical applications.This thesis innovatively introduces the conditions for path partitioning based on practical application scenarios,and proposes graph partitioning problems with paths that are different from graph partitioning problems and hypergraph partitioning problems.Based on the different objective functions,they are divided into two categories:global graph partitioning problems with paths and maximum graph partitioning problems with paths.Through thorough research on existing graph partitioning algorithms and hypergraph partitioning algorithms,this thesis adopts the multilevel graph partitioning algorithm framework and proposes targeted solutions and algorithms for graph partitioning problems with paths.The algorithm is mainly divided into three stages:coarsening,initial partitioning,and refinement.In the coarsening stage,we recalculate the weights of edges based on the characteristics of the objective function,and contract them according to their importance.This reduces the size of the graph while protecting important edges.When the size of the graph is small enough,we use high-quality graph partitioning algorithms to perform initial partitioning on the coarsened graph,obtaining a basic partitioning scheme that meets the constraints of the original graph.In the refinement stage,we continuously optimize the objective function by gradually uncoarsening the coarsened graph while moving vertices to obtain the final partitioning solution.In the process of explaining the algorithm,this thesis focuses on analyzing the mathematical principles and corresponding theoretical support behind the algorithm,and demonstrates the rationality and operability of the solution.For special application scenarios such as nonequivalent partitions,multi-constraint graphs,and dynamic graphs,corresponding solutions have been obtained by combining new technologies with the algorithm proposed in this thesis,demonstrating the good universality of this algorithm.