A parallel approach to the Eulerian cycle problem

A novel parallel approach for constructing Eulerian cycles of a given graph is presented. The proposed approach constitutes a combination of genetic algorithms and artificial neural networks. By tackling the Eulerian cycle problem as a constraint optimization problem, Eulerian cycle existence is determined, and either Eulerian cycles (if they exist) or paths encompassing the greatest possible number of edges (maximal traversal of edges, with edges traversed no more than once) are consistently constructed. Apart from being of theoretical interest, Eulerian cycle existence and construction have recently found significant applications in such areas of VLSI circuit design, RAM fault detection, and CPU access. © 2002 Wiley Periodicals, Inc.