Min-cut optimization algorithm based on cellular automata for bisecting graph
Peng Xuange · Computer Engineering and Applications Journal · 2008
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.