A neural network parallel algorithm for clique vertex-partition problems

Nobuo Funabiki, Yoshiyasu Takefuji, Kuo Chun Lee, Yong Beom Cho

研究成果: Article査読

7 被引用数 (Scopus)


A parallel algorithm based on a neural network model for solving clique vertex-partition problems in arbitrary non-directed graphs is presented in this paper. A clique of a graph G = (V, E) with a set of vertices V and a set of edges E is a complete subgraph of G where any pair of vertices is connected with an edge. A clique vertex-partition problem of a graph G is to partition every vertex in V into a set of disjointed cliques of G. The clique vertex-partition problem with the minimum number of cliques in an arbitrary graph is known to be NP-complete. The algorithm requires nm processing elements for the n vertex m partition problem. A total of 10 different problems with 8 vertex to 300 vertex graphs were examined where the algorithm found a solution in nearly constant time. The circuit diagram of the neural network model is also proposed in this paper.

ジャーナルInternational Journal of Electronics
出版ステータスPublished - 1992 3月

ASJC Scopus subject areas

  • 電子工学および電気工学


「A neural network parallel algorithm for clique vertex-partition problems」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。