A saturated linear dynamical network for approximating maximum clique


Pekergin F., Morgul O., Guzelis C.

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-FUNDAMENTAL THEORY AND APPLICATIONS, cilt.46, ss.677-685, 1999 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 46 Konu: 6
  • Basım Tarihi: 1999
  • Doi Numarası: 10.1109/81.768824
  • Dergi Adı: IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-FUNDAMENTAL THEORY AND APPLICATIONS
  • Sayfa Sayıları: ss.677-685

Özet

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.