A parallel approach to the Eulerian cycle problem

Tatiana Tambouratzis

doi:10.1002/int.10061

2002-11-22

PRE

Tatiana Tambouratzis

DOI：10.1002/int.10061

原文链接

原文求助

摘要

En 中文

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. (C) 2002 Wiley Periodicals, Inc.