无向赋权图剖分优化问题的研究进展

RESEARCH PROGRESS IN THE WEIGHTED UNDIRECTED GRAPH PARTITIONING

无向赋权图剖分优化问题作为图论中的一个典型组合优化问题,在大规模集成电路设计、并行计算、数据挖掘、任务调度、知识发现、图像分割等领域有着广泛的应用。本文给出了无向图剖分优化问题的相关概念;从寻优策略的角度,将无向图剖分优化问题的求解算法分为构造性算法和迭代改进算法;分析了求解无向图剖分优化问题的迁移方法、几何方法、组合方法、谱方法、元胞自动机方法;重点讨论了多水平方法的粗化阶段、初始剖分阶段和优化阶段相应的匹配算法、初始剖分算法和迁移优化算法;介绍了无向图剖分优化问题的典型应用领域并指出了该问题今后的研究方向。

Graph partitioning is a fundamental combinatorial optimization problem of graph theory with extensive applications in many areas, including VLSI design, parallel processing, data mining, task scheduling, knowledge discovery and image segmentation. Firstly, we provide some definitions and conceptions of graph partitioning. Secondly, we divide the graph partitioning algorithm into constructive algorithm and iterative algorithm in the view of optimization strategy. Thirdly, we analyze the graph partitioning algorithm of move-based, geometric, combinatorial, spectral and cellular automata. Furthermore, we discuss matching algorithm of coarsening phase, partitioning algorithm of initial partitioning phase and refinement algorithm of uncoarsening phase in multilevel-based graph partitioning algorithm. Finally, we introduce the application areas of graph partitioning and present the field of further research of graph partitioning.