摘要：

对超图划分问题运用元胞自动机理论进行分析建模，提出一种元胞自动机模型以及基于该模型的赋权超图划分优化算法。在该模型中，元胞对应于赋权超图中的结点，邻接元胞对应于邻接超边所包含的结点，元胞的状态对应于所在的划分子集。引入二维辅助数组存储每条超边在划分子集中的结点个数，给出快速的元胞收益值和划分割切值的计算方法，从而避免遍历超边中的结点。实验结果表明，与赋权图划分算法和迁移方法相比，该算法可以取得更优的划分，且时间复杂度和空间复杂度较低。

关键词: 赋权超图, 划分算法, 元胞自动机, 时间复杂度, 空间复杂度

Abstract:

The Cellular Automata(CA) model for the problem by applying the CA theory and a min-cut partitioning algorithm based on the model for bisecting weighted hypergraph are proposed. In the model, the vertex of hypergraph can be considered as the cell, the vertices of adjacent hypergraph are denoted by the CA-neighborhoods and each cell’s state represents the partitioning which the corresponded vertex belongs to. Furthermore, the two-dimensional auxiliary array is designed for counting the vertices of each hypergraph in different partitions. The rapid method of calculating the cell’s gain and the cut’s size are proposed to avoid traversing each vertex of hypergraph. Experimental results show that the algorithm not only can find the better partitioning of weighted hypergraph than the move-based method and graph parti-tioning algorithm, but also can reduce the time complexity and the space complexity.

Key words: weighted hypergraph, partitioning algorithm, Cellular Automata(CA), time complexity, space complexity

中图分类号: 

• N945.12