Login | Register

An effective algorithm for multiway hypergraph partitioning


An effective algorithm for multiway hypergraph partitioning

Zhao, Zhi Zi (2000) An effective algorithm for multiway hypergraph partitioning. Masters thesis, Concordia University.

[thumbnail of MQ47861.pdf]
Text (application/pdf)


The problem of hypergraph partitioning has been around for more than a quarter of a century. Its early applications were centered on VLSI circuit design. In recent years, the application of hypergraph partitioning has been extended into the areas including data classifications, efficient storage of very large database and data mining. In this thesis, we propose an effective multiway hypergraph partitioning algorithm. We introduce the concept of net gain and embed it in the selection of cell moves. Unlike traditional FM-based iterative improvement algorithms in which the selection of the next cell to move is only based on its cell gain, our selection is based on both cell gains and net gains. To escape from local optima and to search broader solution space, we propose a new perturbation mechanism. These two strategies significantly enhance the solution quality produced by our algorithm. Based on our experimental justification, we also smoothly decrease the number of iterations from pass to pass to reduce the computational effort so that our algorithm can partition large circuits with reasonable run time. Compared with the recent multiway partitioning algorithms proposed by Dasdan and Aykanat, ours significantly outperforms theirs in term of solution quality (cutsize) and run time: the average improvements in terms of average cutsize over their PLM3 (Partitioning by Locked Moves) and PFM3 (Partitioning by Free Moves) are 47.64% and 36.76% with only 37.17% and 9.66% of their run time respectively.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Zhao, Zhi Zi
Pagination:ix, 88 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Tao, Lixin
Identification Number:QA 166.23 Z43 2000
ID Code:1058
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:16
Last Modified:13 Jul 2020 19:48
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top