A Min-Cut-Based Simulated Annealing Algorithm for Graph Bisection

摘要：

Graph bisection is a fundamental problem with applications in many fields of study. Previously, the simulated annealing algorithm has been demonstrated as an efficient tool to deal with this NP-hard problem. In this paper, we propose a min-cut based simulated annealing algorithm to solve the graph bisection problem. This algorithm uses the Stoer-Wagner min-cut algorithm as a procedure to obtain an initial solution, with which the simulated annealing algorithm starts. We run this algorithm and the pure simulated annealing algorithm, i.e., starting with a random initial solution, on the same graphs. The experiment result shows that the algorithm outperforms the pure simulated annealing algorithm.

关键词： minimum cut simulated annealing natural computing graph bisection

作者: Wang Qian

作者单位: Department of Computer Science and Technology, Private Hualian College Guangzhou 510663, China

会议类型: 国际会议

会议名称: 2010 International Conference on Information Security and Artificial Intelligence(2010年信息安全与人工智能国际会议 ISAI 2010)

会议地点: 成都

会议语种:英文

页码: 465-468

在线出版日期: 2010-12-17（万方平台首次上网日期，不代表论文的发表时间）