Finding a minimum circuit in a graph

Abstract

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