Given an undirected graph G, we consider enumerating all Eulerian trails, that is, walks containing each of the edges in G just once. We consider achieving it with the enumeration of Hamiltonian paths with the zero-suppressed decision diagram (ZDD), a data structure that can efficiently store a family of sets satisfying given conditions. First we compute the line graph L(G), the graph representing adjacency of the edges in G. We also formulated the condition when a Hamiltonian path in L(G) corresponds to an Eulerian trail in G because every trail in G corresponds to a path in L(G) but the converse is not true. Then we enumerate all Hamiltonian paths in L(G) satisfying the condition with ZDD by representing them as their sets of edges.
['Hiroyuki Hanada', 'Shuhei Denzumi', 'Yuma Inoue', 'Hiroshi Aoki', 'Norihito Yasuda', 'Shogo Takeuchi', 'Shin-ichi Minato']
Enumerating Eulerian Trails via Hamiltonian Path Enumeration