ON THE M-WAY GRAPH PARTITIONING PROBLEM

Authors
Citation
I. Ahmad et Mk. Dhodhi, ON THE M-WAY GRAPH PARTITIONING PROBLEM, Computer journal, 38(3), 1995, pp. 237-244
Citations number
19
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
ISSN journal
00104620
Volume
38
Issue
3
Year of publication
1995
Pages
237 - 244
Database
ISI
SICI code
0010-4620(1995)38:3<237:OTMGPP>2.0.ZU;2-2
Abstract
The m-way graph partitioning problem (GPP) is an intractable combinato rial optimization problem with many important applications in the desi gn automation of VLSI circuits and in the mapping problem for distribu ted computing systems. In this paper, we introduce a technique based o n a problem-space genetic algorithm (PSGA) for the GPP to reduce the w eighted cut-size while keeping the size of each subset balanced. The p roposed PSGA based approach integrates a problem-specific simple and f ast heuristic with a genetic algorithm to search a large solution spac e efficiently and effectively to find the best possible solution in an acceptable CPU time. Experimental study shows that our technique prod uces better results with respect to both the quality of the solution a nd the computational time over the previous work. The PSGA is a simple , versatile and a generic optimization technique which can also be app lied to other combinatorial optimization problems.