Premium
A note on finding optimum branchings
Author(s) -
Camerini P. M.,
Fratta L.,
Maffioli F.
Publication year - 1979
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230090403
Subject(s) - uniqueness , mathematics , branching (polymer chemistry) , simple (philosophy) , graph , algorithm , mathematical optimization , combinatorics , discrete mathematics , computer science , mathematical analysis , philosophy , materials science , epistemology , composite material
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.