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. An 0(n2) algorithm is presented to find an almost minimum circuit. The straightforward algorithm for finding a minimum circuit has an 0(ne) behavior. It is refined to yield an O(n2) 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 presented. The first has an worst case bound (0(n) for planar graphs); the second takes 0(n5/3) time on the average; the third has an 0(nlog) worst case behavior. For digraphs, recent results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with 0(n2logn) average behavior.