A note on finding optimum branchings
Paolo M. Camerini, Luigi Fratta, Francesco Maffioli · Networks · 1979
Abstract The subject of this note is Tarjan's algorithm for finding an optimum branching in a directed graph. Two errors are pointed out, namely (i) an incorrect claim involving branching uniqueness, and (ii) an imprecise way of updating edge values in each iteration. These two inaccuracies do not affect the basic validity of the algorithm. It is shown here that they may be fixed via a simple modification, which leaves unchanged the overall time and space performances.