An Evolutionary Approach to the Eulerian Cycle Problem

that uses every edge exactly once. It is
well known that such a cycle exists if and only
if all vertices of the graph are of even degree.
The problem of finding an Eulerian cycle can be
solved in O(m) where m is the number of edges
of the graph.

The theoretic runtime analysis of evolutionary
algorithms is a field of growing interest in the
rather practically oriented research community of
evolutionary computation. We investigate how
different variants of a basic evolutionary
algorithm perform on the Eulerian cycle problem
and determine their expected runtime. We cannot
expect a generic framework to outperform a
problem-tailored algorithm, still one of the
variants solves the Eulerian cycle problem in
O(m log m).