Enumeration of the Elementary Circuits of a Directed Graph

Abstract

An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm is based on a backtracking procedure of Tiernan, but uses a lookahead and labeling technique to avoid unnecessary work. It has a time bound of $O((V \cdot E)(C + 1))$ when applied to a graph with V vertices, E edges, and C elementary circuits.