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

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