文献类型：期刊文章

作　　者：孙凌宇[1] 冷明[1] 彭宣戈[1]

机构地区：[1]井冈山学院计算机科学系,江西吉安343009

出　　处：《计算机工程与应用》

基　　金：科技部国际合作项目(NoCB7-2-01);江西省教育规划资助项目(No04BY453)

年　　份：2008

卷　　号：44

期　　号：24

起止页码：46-49

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、ZGKJHX、核心刊

摘　　要：运用元胞自动机理论,针对无向图剖分优化问题进行了分析和建模,提出了一种元胞自动机模型以及基于该模型的无向图剖分优化算法。在该元胞自动机模型中,元胞对应于无向图中的结点,元胞的邻居对应于邻接结点,元胞空间对应于无向图中的结点集,元胞的状态对应于所在的结点子集。实验及分析表明该算法不仅能找到无向图的近似最优剖分,而且有效地降低了空间复杂度和时间复杂度。

关 键 词：元胞自动机 无向图 优化算法 复杂度

分 类 号：TP391]