J. Sack

Enumerating Length-Bounded Simple Paths and Cycles in Directed Graphs with O(k(n+m)) Delay Using Edge-Consistent Node Barriers

Enumerating simple paths and cycles subject to a given length bound is a fundamental problem in graph algorithms. Recent algorithms, namely BC-DFS (Peng et al. 2019, 2021) and CYCLE_SEARCH (Gupta and Suzumura 2021, arXiv:2105.10094v2), employ cached barrier values to prune fruitless searches. Both algorithms turn out t...