Graph partition is a classical combinatorial optimization and graph theory problem,and it has a lot of applications,such as scientific computing,VLSI design and clustering etc.In this paper,we study the partition prob...Graph partition is a classical combinatorial optimization and graph theory problem,and it has a lot of applications,such as scientific computing,VLSI design and clustering etc.In this paper,we study the partition problem on large scale directed graphs under a new objective function,a new instance of graph partition problem.We firstly propose the modeling of this problem,then design an algorithm based on multi-level strategy and recursive partition method,and finally do a lot of simulation experiments.The experimental results verify the stability of our algorithm and show that our algorithm has the same good performance as METIS.In addition,our algorithm is better than METIS on unbalanced ratio.展开更多
基金supported by National Numerical Windtunnel Project(No.NNW2019ZT5-B16)National Natural Science Foundation of China(Nos.11871256,12071194)the Basic Research Project of Qinghai(No.2021-ZJ-703).
文摘Graph partition is a classical combinatorial optimization and graph theory problem,and it has a lot of applications,such as scientific computing,VLSI design and clustering etc.In this paper,we study the partition problem on large scale directed graphs under a new objective function,a new instance of graph partition problem.We firstly propose the modeling of this problem,then design an algorithm based on multi-level strategy and recursive partition method,and finally do a lot of simulation experiments.The experimental results verify the stability of our algorithm and show that our algorithm has the same good performance as METIS.In addition,our algorithm is better than METIS on unbalanced ratio.
