A Method of Improving Initial Partition of Fiduccia-Mattheyses Algorithm

作     者：Sheblaev, M. V. Sheblaeva, A. S. 

作者机构：LomonosovMoscow State Univ Fac Space Res Moscow 119991 Russia LomonosovMoscow State Univ MSEC Moscow 119991 Russia 

出 版 物：《LOBACHEVSKII JOURNAL OF MATHEMATICS》 (罗巴切夫斯基数学杂)

年 卷 期：2018年第39卷第9期

页      面：1270-1276页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：balanced graph partitioning Fiduccia-Mattheyses algorithm FM algorithm min-cut balanced cut 

摘      要：This article presents a new method for finding initial partitioning for Fiduccia-Mattheyses algorithm that makes it possible to work out a qualitative approximate solution for the original balanced hypergraph partitioning problem. The proposed method uses geometrical properties and dimension reduction methods for metric spaces of large dimensions.