Answers are grounded in this paper and cite their sources.
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(n2). 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.
No takes yet. Share an insight, caveat, or question.
Robert E. Tarjan (1977) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: