Communications of the ACM · 1969 · 172 citations · 3 references
ComputingComputer ScienceAlgorithmsCombinatoricsTheory Of ComputationAlgorithm AnalysisComputational ComplexityDirected Acyclic GraphsGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsCycle DetectionGraph Traversal AlgorithmsSpanning Tree Construction
A fast method is presented for finding a fundamental set of cycles for an undirected finite graph. The algorithm grows a spanning tree, iteratively examining vertices via a pushdown list, adding edges to the tree or forming fundamental cycles when encountering already‑tree vertices. The algorithm requires O(n²) storage and runs in O(n^γ) time with 2 ≤ γ ≤ 3, achieving the lower bound on random graphs and outperforming previous methods in speed and storage.
A fast method is presented for finding a fundamental set of cycles for an undirected finite graph. A spanning tree is grown and the vertices examined in turn, unexamined vertices being stored in a pushdown list to await examination. One stage in the process is to take the top element v of the pushdown list and examine it, i.e. inspect all those edges ( v, z ) of the graph for which z has not yet been examined. If z is already in the tree, a fundamental cycle is added; if not, the edge ( v, z ) is placed in the tree. There is exactly one such stage for each of the n vertices of the graph. For large n , the store required increases as n 2 and the time as n γ where γ depends on the type of graph involved. γ is bounded below by 2 and above by 3, and it is shown that both bounds are attained. In terms of storage our algorithm is similar to that of Gotlieb and Corneil and superior to that of Welch; in terms of speed it is similar to that of Welch and superior to that of Gotlieb and Corneil. Tests show our algorithm to be remarkably efficient ( γ = 2) on random graphs.
3