A comparison of three algorithms for finding fundamental cycles in a directed graph

✍ Scribed by Doris R. Ryan; Stephen Chen

• Publisher: John Wiley and Sons
• Year: 1981
• Tongue: English
• Weight: 543 KB
• Volume: 11
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230110102

✦ Synopsis

Abstract

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.