A Novel Coarsening Scheme for Multilevel Graph Partitiong

摘要：

When applying multilevel scheme to solve the static graph partitioning problem, shortcomings and limitations exist in the state-of-the-art coarsening schemes depend mainly on finding maximal matchings to obtain the successively coarse graphs, especially for partitioning irregular graphs, which can cause the multilevel algorithms to produce poor-quality solutions. This paper proposes an improved coarsening scheme by re-collapsing the matching in each coarsening step. The new coarsening scheme is more effective in quality, which is proved to be effective by both theoretical analysis and experimental results.

关键词： Graph partitioning multilevel scheme graph coarsening

作者: Lu Yao Zhenghua Wang Zongzhe Li Wei Cao Yongxian Wang

作者单位: School of Computer Science, National University of Defense Technology, Changsha, China

会议类型: 国际会议

会议名称: 2011 4th International Conference on Biomedical Engineering and Informatics(第四届生物医学工程与信息学国际会议 BMEI 2011)

会议地点: 上海

会议语种:英文

页码: 2104-2107

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