Neural computing for the m-way graph partitioning problem

Takayuki Saito, Yoshiyasu Takefuji

研究成果: Article査読

1 被引用数 (Scopus)


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 m-way graph partitioning problem is proposed where the maximum neuron model is used. The unidirected 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 m-way graph partitioning problem in terms of the computation time and the solution quality.

ジャーナルIEICE Transactions on Information and Systems
出版ステータスPublished - 1997 9月 1

ASJC Scopus subject areas

  • ソフトウェア
  • ハードウェアとアーキテクチャ
  • コンピュータ ビジョンおよびパターン認識
  • 電子工学および電気工学
  • 人工知能


「Neural computing for the m-way graph partitioning problem」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。