V. V. Kureichik, Dr. Tech. Sci., Professor, Head of CAD Department, å-mail: vkur@sfedu.ru, Southern Federal University, Rostov-on-don, 344006, Russian Federation, Vl. Vl. Kureichik, Ph.D., Principal Engineer, e-mail: kureichik@yandex.ru, "Gazprom subterranean repair Urengoy" LLC, Saint-Petersburg, 190000, Russian Federation

Graph Partitioning Based on the Combined Approach

The article considers one of the most important combinatorial optimization problems — the problem of graph partitioning. It belongs to the class of NP-complex optimization problems. The article presents the partitioning problem statement. Due to the complexity of this task, the article proposes a new search strategy based on a combined approach. The combined approach is to divide the decision-making process into two levels. At the first level, the bee optimization method is used to quickly obtain subdomains with a high value of the objective function, and at the second level, an evolutionary algorithm is used to improve obtained solutions. To implement this approach, the authors developed a combined algorithm that can obtain sets of quasi-optimal solutions in polynomial time and avoid looping in local regions at the same time. A software module is developed and algorithms for partitioning graphs into parts are implemented. A computational experiment has been carried out when dividing into 8 parts of test circuits (benchmarks) by IBM. An analysis of experimental studies showed that the developed combined algorithm is on average 5 % higher than the partition results obtained by well-known hMetis, PGAComplex algorithms with comparable solution time, which indicates the effectiveness of the proposed approach. The time complexity of the developed combined algorithm is approximately O (n²).
Keywords: graph partitioning, combined approach, combined algorithm, bee colony optimization, evolutionary algorithm

P. 667–672