2015 | OriginalPaper | Buchkapitel
Enumerating Eulerian Trails via Hamiltonian Path Enumeration
Autoren: Hiroyuki Hanada, Shuhei Denzumi, Yuma Inoue, Hiroshi Aoki, Norihito Yasuda, Shogo Takeuchi, Shin-ichi Minato
Verlag: Springer International Publishing
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.
