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

• 作者: 冷明 孙凌宇 朱平 边计年 马昱春
• 来源期刊: 计算机工程
• 学科: 地球科学
• 关键词: 赋权超图 划分算法 元胞自动机 时间复杂度 空间复杂度
• 年，卷（期）: 2012,（15）
• 所属期刊栏目: 专栏
• 页码范围: 23-27
• 分类号: N945.12
• 字数: 6746字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2012.15.007

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	边计年	清华大学计算机科学与技术系	50	326	9.0	16.0
2	孙凌宇	井冈山大学计算机科学系	46	236	7.0	12.0
3	冷明	井冈山大学计算机科学系	52	211	7.0	11.0
5	朱平	井冈山大学计算机科学系	24	109	6.0	9.0
8	马昱春	清华大学计算机科学与技术系	15	48	4.0	6.0