ON THE DELAY TIME IN THE ENUMERATION OF ALL SIMPLE CYCLES OF A DIRECTED GRAPH

For the fundamental problem of enumeration of all simple cycles of a given directed graph with n vertices and m edges, it is known that the delay time between successive outputs of two simple cycles is \(\mathcal {O}(n+m)\) $\mathcal{O}(n+m)$ where \(m \in \mathcal {O}(n^2)\) $m\in \mathcal{O}(n^2)$ . This paper shows that for a directed graph under a uniform probability distribution for the out-degrees of the vertices in the graph, all simple cycles of the graph can be listed with delay time \(\mathcal {O}(n \ln n)\) $\mathcal{O}(nlnn)$ in expectation.