Finding optimum branchings

Chu and Liu, Edmonds, and Bock have independently devised an efficient algorithm to find an optimum branching in a directed graph. We give an implementation of the algorithm which runs in 0(m logn) time if the problem graph has n vertices and m edges. A modification for dense graphs gives a running time of 0(n²). We also show that the unmodified algorithm runs in 0(n(log n)² +m) time on an average graph, assuming a uniform probability distribution.