• 专栏 •

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

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.