## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 357-372 |

Number of pages | 16 |

Journal | International Journal of Electronics |

Volume | 72 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1992 Mar |

Externally published | Yes |

## ASJC Scopus subject areas

- Electrical and Electronic Engineering