计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (24): 46-49.DOI: 10.3778/j.issn.1002-8331.2008.24.012

• 理论研究 • 上一篇    下一篇

一种基于元胞自动机的无向图剖分优化算法

孙凌宇1,冷 明1,2,彭宣戈1   

  1. 1.井冈山学院 计算机科学系,江西 吉安 343009
    2.上海大学 计算机工程与科学学院,上海 200072
  • 收稿日期:2007-10-22 修回日期:2008-01-21 出版日期:2008-08-21 发布日期:2008-08-21
  • 通讯作者: 孙凌宇

Min-cut optimization algorithm based on cellular automata for bisecting graph

SUN Ling-yu1,LENG Ming1,2,PENG Xuan-ge1   

  1. 1.Computer Science Department,Jinggangshan College,Ji’an,Jiangxi 343009,China
    2.School of Computer Engineering and Science,Shanghai University,Shanghai 200072,China
  • Received:2007-10-22 Revised:2008-01-21 Online:2008-08-21 Published:2008-08-21
  • Contact: SUN Ling-yu

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

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

Abstract: According to the analysis of min-cut partitioning problem,we give a Cellular Automata(CA) model for this problem by applying the cellular automata theory and propose a min-cut optimization algorithm based on this model for bisecting graph.In the model,the vertex of graph can be considered as the cell and the adjacent vertices have been denoted by the CA-neighborhoods.Furthermore,the CA-space denotes the set of vertices and each cell’s state represents the subset of vertices which the corresponded vertex belongs at.The experiment and the analysis show that our algorithm not only can find good approximate partitioning of undirected graph,moreover can reduce the time complexity and the space complexity effectively.

Key words: cellular automata, undirected graph, optimization algorithm, complexity