A search algorithm for finding the simple cycles of a directed graph
Loading...
Files
Date
1974
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Two efficient algorithms, that admit each simple cycle once in searching the ares of a digraph, are presented and a proof of the algorithms provided. The first algorithm is nonadaptive while the second is an adaptive one. Since they extract cycles directly, they require less storage than Weinblatt. Since the method of search of the first is more efficient than Tiernan, it is faster than Tiernan. An example used by Tiernan is given for comparison. The speed is discussed in relation to number of vertices, arcs, and simple cycles. The storage requirement is 0(n). The adaptive version has a theoretical speed bound by O(c.m.n), where c is the number of cycles, m the number of arcs, and n the number of vertices. Both algorithms are bounded by 0(N[subscript c] .m) on the complete graph where Ν[subscript c] is the number of cycles of the complete graph.