A parallel computation network for the maximum clique problem

Author

Lin, Fuyau

Author_Institution

Dept. of Comput. Eng. Santa Clara Univ., CA, USA

fYear

1993

fDate

3-6 May 1993

Firstpage

2549

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on

Conference_Location

Chicago, IL

Print_ISBN

0-7803-1281-3

Type

conf

DOI

10.1109/ISCAS.1993.394285

Filename

394285