Breadcrumb

 
 

An effective algorithm for multiway hypergraph partitioning

Title:

An effective algorithm for multiway hypergraph partitioning

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

[img]
Preview
PDF
2877Kb

Abstract

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 > Faculty 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:Theses (M.Comp.Sc.)
Program:Computer Science and Software Engineering
Date:2000
Thesis Supervisor(s):Tao, Lixin
ID Code:1058
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:16
Last Modified:08 Dec 2010 10:18
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

Document Downloads

More statistics for this item...

Concordia University - Footer