Solving the maximum cut problem using two-phase Hopfield neural network

The goal of maximum cut problem is to partition the vertex set of an undi- rected graph into two parts in order to maximize the cardinality of the set of edges cut by the partition. Many optimization problems can be formulated in terms of finding the maximum cut in a network or a graph. In this paper, we present a two-phase Hopfield network algorithm for maximum cut problem. The proposed method can be divided into two phases. The first phase uses the Hopfield network to find a local minimum which cor- responds a near-maximum solution of the problem. The second phase makes the network escape from the state of the near-maximum solution to maximum solution or a better one by updating the state of neurons using another neural network. A large number of instances are simulated to verify the proposed method with the simulation results show- ing that the proposed algorithm is much better than the previous works for solving the maximum cut problem. ICIC International