For a given graph G(V, E), a subset M of E is called a maximal matching of G if no pair of edges in M is adjacent to each other and no other matching M′ such as M ⊂ M′ exists for G. In this paper, we present a neural network parallel algorithm for the minimum maximal matching problem. This NP-complete problem requires to find a maximal matching composed of the least number of edges in G. The neural network consists of N × N binary neurons for the N-vertex graph problem. In order to improve the solution quality, we introduce a heuristic term into the motion equation for a diagonal neuron which represents the exclusion of the vertex from the matching. We verify the performance through simulations using random graphs, where our neural network finds better solutions than the greedy algorithm and the simulated annealing.
