A NEURAL NETWORK MODEL FOR FINDING A NEAR-MAXIMUM CLIQUE

被引：26

作者：

FUNABIKI, N

TAKEFUJI, Y

LEE, KC

机构：

[1] CASE WESTERN RESERVE UNIV,DEPT ELECT ENGN & APPL PHYS,CLEVELAND,OH 44106

[2] CIRRUS LOG INC,DEPT RES & DEV,FREMONT,CA 94538

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 1992年 / 14卷 / 03期

关键词：

D O I：

10.1016/0743-7315(92)90072-U

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A parallel algorithm based on the neural network model for finding a near-maximum clique is presented in this paper. A maximum clique of a graph G is a maximum complete subgraph of G where any two vertices are adjacent. The problem of finding a maximum clique is NP-complete. The parallel algorithm requires n processing elements for an n-vertex graph problem. The algorithm is verified by solving 230 different graph problems. The simulation results show that our computation time on a Macintosh IIfx is shorter than that of two better known algorithms on a Cray 2 and an IBM 3090 while the solution quality is similar. The algorithm solves a near-maximum clique problem in nearly constant time on a parallel machine with n processors. © 1992.

引用

页码：340 / 344

页数：5

共 14 条

[1] FINDING A MAXIMUM CLIQUE IN AN ARBITRARY GRAPH [J].