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

Authors

• Alon Itai

Keywords

No keywords are indexed for this paper.