Constant amortized time enumeration of Eulerian trails
Constant amortized time enumeration of Eulerian trails
复制标题
欧拉轨迹的常数摊销时间枚举
DOI：
10.1016/j.tcs.2022.04.048
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Wasa Kunihiro
中科院分区：
文献类型：
--
作者：
Kurita Kazuhiro;Wasa Kunihiro
本文考虑边不同和点不同欧拉路的计数问题。如果边序列不同，则称两条欧拉迹是边不同的；如果两个点序列不相同，则称它们是点不同的。为了解决这些问题，我们提出了总运行时间为O(N+m)的最优计数算法，其中N是解的个数，m是输入连通图的边数。所提出的算法基于[Avis and Fukuda，DAM 1996]引入的反向搜索技术和[Uno，WADS 2015]引入的推出摊销技术。
In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinct if the edge sequences are not identical, and they are said to be vertex-distinct if the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O (N+ m) total time, where N is the number of solutions and m is the number of edges in an input connected graph. The proposed algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push-out amortization technique introduced by [Uno, WADS 2015].