An efficient parallel algorithm for the minimum crossing number problem

Rong‐Long Wang

doi:10.1016/j.neucom.2004.09.005

Return

An efficient parallel algorithm for the minimum crossing number problem

2005-08-01

PRE

Rong‐Long Wang *

Kozo Okazaki

DOI：10.1016/j.neucom.2004.09.005

Original

Original request for help

Save

Abstract

En 中文

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. (c) 2005 Elsevier B.V. All rights reserved.

Keywords:

minimum crossing number problem

NP-complete problem

Hopfield neural network

internal dynamics

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.