Premium
A parallel approach to the Eulerian cycle problem
Author(s) -
Tambouratzis Tatiana
Publication year - 2002
Publication title -
international journal of intelligent systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.291
H-Index - 87
eISSN - 1098-111X
pISSN - 0884-8173
DOI - 10.1002/int.10061
Subject(s) - eulerian path , tree traversal , constraint (computer aided design) , computer science , very large scale integration , parallel computing , algorithm , graph traversal , theoretical computer science , mathematical optimization , mathematics , embedded system , geometry , lagrangian
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.