Premium
A comparison of three algorithms for finding fundamental cycles in a directed graph
Author(s) -
Ryan Doris R.,
Chen Stephen
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110102
Subject(s) - algorithm , directed graph , mathematics , spanning tree , arc (geometry) , graph , computer science , generator (circuit theory) , tree (set theory) , combinatorics , power (physics) , physics , geometry , quantum mechanics
Given a connected directed graph and a spanning tree, we consider the problem of finding the set of fundamental cycles. In particular, for each cotree arc i and tree arc j , we need to know whether or not i and j are in the same fundamental cycle, and if so, whether or not arcs i and j are oriented in the same direction. This problem has application in primal network flow, longest cycle, and all‐cycle algorithms. In this paper, we describe and compare three algorithms for finding fundamental cycles. Computational results are presented on a variety of directed graphs produced by a network generator. Although each of the algorithms has worst case complexity O(kp) , where k and p are the number of cotree arcs and nodes, respectively, a variation of a root traceback algorithm is shown to be the fastest in almost all cases.