Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
Ronald C. Read, Robert Endre Tarjan · Networks · 1975
ABSTRACT Backtrack algorithms for listing certain kinds of subgraphs of a graph are described and analyzed. Included are algorithms for listing all spanning trees, all cycles, all simple cycles, or all of certain other kinds of paths. The algorithms have 0(V+E) space requirements and 0(V+E+EN) time requirements, if the problem graph has V vertices, E edges, and N subgraphs of the type to be listed.