计算机工程 ›› 2012, Vol. 38 ›› Issue (15): 23-27.doi: 10.3969/j.issn.1000-3428.2012.15.007

• 专栏 • 上一篇    下一篇

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

冷 明1,2,孙凌宇1,边计年2,马昱春2,朱 平1   

  1. (1. 井冈山大学计算机科学系,江西 吉安 343009;2. 清华大学计算机科学与技术系,北京 100084)
  • 收稿日期:2011-12-20 出版日期:2012-08-05 发布日期:2012-08-05
  • 作者简介:冷 明(1975-),男,副教授、博士、CCF会员,主研方向:VLSI算法分析与设计;孙凌宇,副教授、硕士;边计年,教授、博士生导师、CCF高级会员;马昱春,副教授;朱 平,教授
  • 基金项目:

    国家自然科学基金资助项目(61063007, 61163062, 61106030);江西省自然科学基金资助项目(2009GQS0060);江西省教育厅科学技术研究基金资助项目(GJJ12474, GJJ10201, GJJ09590, 赣教技字[2007]320号)

Research on Cellular Automata Model of Hypergraph Partitioning Problem and Its Algorithm

LENG Ming 1,2, SUN Ling-yu 1, BIAN Ji-nian 2, MA Yu-chun 2, ZHU Ping 1   

  1. (1. Department of Computer Science, Jinggangshan University, Ji’an 343009, China; 2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)
  • Received:2011-12-20 Online:2012-08-05 Published:2012-08-05

摘要:

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

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

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

中图分类号: