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 2 ). We also show that the unmodified algorithm runs in 0(n(log n) 2 +m) time on an average graph, assuming a uniform probability distribution.