A saturated linear dynamical network for approximating maximum clique

We use a saturated linear gradient dynamical network for finding an approximate solution to the maximum clique problem. We show that for almost all initial conditions, any solution of the network defined on a closed hypercube reaches one of the vertices of the hypercube, and any such vertex correspo...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on circuits and systems. 1, Fundamental theory and applications Fundamental theory and applications, 1999-06, Vol.46 (6), p.677-685
Main Authors: Pekergin, F., Morgui, O., Guzelis, C.
Format: Article
Language:English
Subjects:
Applied sciences
Cost function
Design optimization
Electric, optical and optoelectronic circuits
Electronics
Equations
Exact sciences and technology
Hopfield neural networks
Hypercubes
Neural networks
Optimization methods
Power system modeling
Real time systems
Traveling salesman problems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We use a saturated linear gradient dynamical network for finding an approximate solution to the maximum clique problem. We show that for almost all initial conditions, any solution of the network defined on a closed hypercube reaches one of the vertices of the hypercube, and any such vertex corresponds to a maximal clique. We examine the performance of the method on a set of random graphs and compare the results with those of some existing methods. The proposed model presents a simple continuous, yet powerful, solution in approximating maximum clique, which may outperform many relatively complex methods, e.g., Hopfield-type neural network based methods and conventional heuristics.
ISSN:1057-7122
1558-1268
DOI:10.1109/81.768824