Title :
A parallel computation network for the maximum clique problem
Author_Institution :
Dept. of Comput. Eng. Santa Clara Univ., CA, USA
Abstract :
The maximum clique problem is to find the maximum complete subgraph of a given graph G. A computation model for large-scale maximum clique problems is proposed and was tested. A parallel algorithm based on the maximum neural network which resembles the winner-takes-all circuit is introduced which solves large-scale problems in reasonable computation time that the best known algorithms cannot solve. The maximum clique problem is first formulated as an unconstrained quadratic zero-one programming problem and is solved by minimizing the weight summation over the same partition in a newly constructed graph
Keywords :
computational complexity; graph theory; integer programming; neural nets; parallel algorithms; quadratic programming; computation model; computation time; large-scale problems; maximum clique problem; maximum complete subgraph; maximum neural network; parallel algorithm; parallel computation network; unconstrained quadratic zero-one programming problem; weight summation; winner-takes-all circuit; Artificial neural networks; Circuits; Compaction; Computer networks; Concurrent computing; Large-scale systems; Neural networks; Programmable logic arrays; Quadratic programming; Very large scale integration;
Conference_Titel :
Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on
Conference_Location :
Chicago, IL
Print_ISBN :
0-7803-1281-3
DOI :
10.1109/ISCAS.1993.394285
