
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Neural Computing for the mWay Graph Partitioning Problem
Takayuki SAITO Yoshiyasu TAKEFUJI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E80D
No.9
pp.942947 Publication Date: 1997/09/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Architectures, Algorithms and Networks for Massively Parallel Computing) Category: Algorithms Keyword: neural network, graph partitioning, heuristic algorithm, combinatorial optimization,
Full Text: PDF>>
Summary:
The graph partitioning problem is a famous combinatorial problem and has many applications including VLSI circuit design, task allocation in distributed computer systems and so on. In this paper, a novel neural network for the mway graph partitioning problem is proposed where the maximum neuron model is used. The undirected graph with weighted nodes and weighted edges is partitioned into several subsets. The objective of partitioning is to minimize the sum of weights on cut edges with keeping the size of each subset balanced. The proposed algorithm was compared with the genetic algorithm. The experimental result shows that the proposed neural network is better or comparable with the other existing methods for solving the mway graph partitioning problem in terms of the computation time and the solution quality.

