Multi-level direct K-way hypergraph partitioning with multiple constraints and fixed vertices

详细信息    查看全文

• 作者：Cevdet Aykanat ; B. Barla Cambazoglu ; Bora Uç ; ar
• 关键词：Hypergraph partitioning ; Multi-level paradigm ; Recursive bisection ; Direct ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6WKJ-4PV94B0-2&_mathId=mml4&_user=1067359&_cdi=6908&_rdoc=5&_acct=
• 刊名：Journal of Parallel and Distributed Computing
• 出版年：2008
• 出版时间：May 2008
• 年：2008
• 卷：68
• 期：5
• 页码：609-625
• 全文大小：512 K

文摘

K-way hypergraph partitioning has an ever-growing use in parallelization of scientific computing applications. We claim that hypergraph partitioning with multiple constraints and fixed vertices should be implemented using direct K-way refinement, instead of the widely adopted recursive bisection paradigm. Our arguments are based on the fact that recursive-bisection-based partitioning algorithms perform considerably worse when used in the multiple constraint and fixed vertex formulations. We discuss possible reasons for this performance degradation. We describe a careful implementation of a multi-level direct K-way hypergraph partitioning algorithm, which performs better than a well-known recursive-bisection-based partitioning algorithm in hypergraph partitioning with multiple constraints and fixed vertices. We also experimentally show that the proposed algorithm is effective in standard hypergraph partitioning.