Finding a Minimum Circuit in a Graph

Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. To find an almost minimum circuit an O(n² ) algorithm is presented. A direct algorithm for finding a minimum circuit has an $O(ne)$ behavior. It is refined to yield an O(n² ) average time algorithm. An alternative method is to reduce the problem of finding a minimum circuit to that of finding a triangle in an auxiliary graph. Three methods for finding a triangle in a graph are given. The first has an O(e3/2) worst case bound ($O(n)$ for planar graphs); the second takes O(n5/3) time on the average; the third has an O(nlog 7 ) worst case behavior. For digraphs, results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with O(n² log n) average behavior.