Enumerating Eulerian Trails via Hamiltonian Path Enumeration
Enumerating Eulerian Trails via Hamiltonian Path Enumeration
复制标题
通过哈密顿路径枚举枚举欧拉路径
DOI：
10.1007/978-3-319-15612-5_15
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
and Shin-ichi Minato
中科院分区：
文献类型：
--
作者：
Hiroyuki Hanada;Shuhei Denzumi;Yuma Inoue;Hiroshi Aoki;Norihito Yasuda;Shogo Takeuchi;and Shin-ichi Minato
给出一个无向图G，我们考虑枚举所有欧拉路，即包含G中每条边的行走仅一次。我们考虑通过用零抑制决策图(ZDD)枚举哈密顿路径来实现这一点，ZDD是一种可以有效地存储满足给定条件的集族的数据结构。首先，我们计算直线图L(G)，该图表示边的邻接。我们还给出了哈密尔顿路INL(G)对应于欧拉迹ING的条件，因为每条路ING对应于一条路INL(G)，但反之亦然。然后，我们通过将满足条件的哈密顿路表示为它们的边集来计数满足ZDD条件的所有哈密顿路。
Given an undirected graphG, we consider enumerating all Eulerian trails, that is, walks containing each of the edges inGjust once. We consider achieving it with the enumeration of Hamiltonian paths with thezero-suppressed decision diagram(ZDD), a data structure that can efficiently store a family of sets satisfying given conditions. First we compute theline graphL(G), the graph representing adjacency of the edges inG. We also formulated the condition when a Hamiltonian path inL(G) corresponds to an Eulerian trail inGbecause every trail inGcorresponds to a path inL(G) but the converse is not true. Then we enumerate all Hamiltonian paths inL(G) satisfying the condition with ZDD by representing them as their sets of edges.
4-正则图中计算欧拉游览的复杂性
影响因子：
1.1
作者：
Qi Ge;Daniel Stefankovic
通讯作者：
Daniel Stefankovic
可解决的自我回避行走问题*)
DOI：
10.1016/s0031-8914(63)80241-4
发表时间：
1963
期刊：
Physica D: Nonlinear Phenomena
影响因子：
--
作者：
P. W. Kasteleyn
通讯作者：
P. W. Kasteleyn