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 (e^3/2) worst case bound (O (n) for planar graphs) ; the second takes O (n^5/3) time on the average; the third has an O (n^ 7) worst case behavior. For digraphs, results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with O (n² n) average behavior.