Use of dynamic trees in a network simplex algorithm for the maximum flow problem (Q1176566)

\textit{D. Goldfarb} and \textit{J. Hao} [ibid., Ser. A 47, No. 3, 353-365 (1990; Zbl 0713.90028)] proposed a pivot rule for the primal network simplex algorithm that solves a maximum flow problem on an \(n\)-vertex, \(m\)-arc network in at most \(nm\) pivots and \(O(n^ 2m)\) time. Here the authors describe how to extend the dynamic tree data structure of \textit{D. D. Sleator} and the third author [J. Comput. Syst. Sci. 26, 362-391 (1983; Zbl 0509.68058)] to reduce the running time of this algorithm to \(O(nm\cdot\log n)\). Though this bound is worse than an \(O(nm\cdot\log(n^ 2/m))\)-time bound by the same authors, their extension of dynamic trees is interesting in its own right. It can be used to find, for example, the strength of a network and its reinforcement, attack and density of a network and other network invariants.