A Hopfield network learning method for bipartite subgraph problem

In this paper, we present a gradient ascent learning method of the Hopfield neural network for bipartite subgraph problem. The method is intended to provide a near-optimum parallel algorithm for solving the bipartite subgraph problem. To do this we use the Hopfield neural network to get a near-maximum bipartite subgraph, and increase the energy by modifying weights in a gradient ascent direction of the energy to help the network escape from the state of the near-maximum bipartite subgraph to the state of the maximum bipartite subgraph or better one. A large number of instances are simulated to verify the proposed method with the simulation results showing that the solution quality is superior to that of best existing parallel algorithm. We also test the learning method on total coloring problem. The simulation results show that our method finds optimal solution in every test graph.