Maximum Cut Computation: Hopfield Neural Network

EasyChair Preprint 15691

Abstract

In  this  research  paper, the  problem  of  computing  the  maximum   cut   in  a  graph  is  shown  to  be equivalent to  finding  the  global  minimum  of  energy  function  of  the  associated  Hopfield  Neural  Network (HNN) . It  is  reasoned  that  using  the  initial  condition  based  on  the  smallest  eigenvector of  synaptic  weight  matrix ( i.e.  eigenvector  corresponding  to  smallest  eigenvalue ), in  the  serial  mode of  operation,  HNN  reaches the  global  minimum  of  associated  energy  function ( quadratic  form  with  the  threshold  vector  being  zero ). Thus, maximum  cut  can  be  determined  using  HNN  in  serial  mode  of  operation.

Keyphrases: Eigenvector, Hopfield neural network, Quadratic Energy Function, Smallest Eigenvector, stable state

@booklet{EasyChair:15691,
  author    = {Rama Murthy Garimella},
  title     = {Maximum  Cut  Computation:  Hopfield  Neural   Network},
  howpublished = {EasyChair Preprint 15691},
  year      = {EasyChair, 2025}}