A NEURAL NETWORK PARALLEL ALGORITHM FOR CLIQUE VERTEX-PARTITION PROBLEMS

被引:6
作者
FUNABIKI, N
TAKEFUJI, Y
LEE, KC
CHO, YB
机构
[1] CASE WESTERN RESERVE UNIV,DEPT ELECT ENGN & APPL PHYS,CLEVELAND,OH 44106
[2] CIRRUS LOG INC,DEPT RES & DEV,FREMONT,CA
关键词
D O I
10.1080/00207219208925578
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
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.
引用
收藏
页码:357 / 372
页数:16
相关论文
共 26 条
[1]  
Carey M. R., 1979, COMPUTERS INTRACTABI
[2]   CLIQUE PARTITIONS AND CLIQUE COVERINGS [J].
ERDOS, P ;
FAUDREE, R ;
ORDMAN, ET .
DISCRETE MATHEMATICS, 1988, 72 (1-3) :93-101
[3]  
Funabiki N., 1991, Neurocomputing, V3, P97, DOI 10.1016/0925-2312(91)90052-D
[4]   A PARALLEL ALGORITHM FOR ALLOCATION OF SPARE CELLS ON MEMORY CHIPS [J].
FUNABIKI, N ;
TAKEFUJI, Y .
IEEE TRANSACTIONS ON RELIABILITY, 1991, 40 (03) :338-346
[5]  
FUNABIKI N, 1991, IN PRESS J PARALLEL
[6]  
FUNABIKI N, 1991, IN PRESS IEEE T COMM
[7]  
FUNABIKI N, 1991, IN PRESS IEEE T CAD
[8]   CLIQUE PARTITIONS OF THE COCKTAIL-PARTY GRAPH [J].
GREGORY, DA ;
MCGUINNESS, S ;
WALLIS, W .
DISCRETE MATHEMATICS, 1986, 59 (03) :267-273
[9]   FACETS OF THE CLIQUE PARTITIONING POLYTOPE [J].
GROTSCHEL, M ;
WAKABAYASHI, Y .
MATHEMATICAL PROGRAMMING, 1990, 47 (03) :367-387
[10]  
HOPFIELD JJ, 1985, BIOL CYBERN, V52, P141