超图划分问题的元胞自动机模型及算法研究 (2012年)

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