An efficient parallel algorithm for the minimum crossing number problem

An efficient parallel algorithm for the minimum crossing number problem is presented. The algorithm, which is designed to embed the edges of a graph such that the total number of crossings is minimized, is based on an improved Hopfield neural network in which the internal dynamics is modified to permit temporary increases of the energy function so that the network can escape from local minima. The proposed algorithm is tested on several complete graphs and the simulation results show that the proposed algorithm provides a high probability of finding optimal solutions.