Babenko, M. A. A fast algorithm of constructing decomposition of multipole flows. (Russian, English) Zbl 1114.94308 Vestn. Mosk. Univ., Ser. I 2006, No. 2, 52-54 (2006); translation in Mosc. Univ. Math. Bull. 61, No. 2, 38-40 (2006). The author proposes an algorithm which, for a given in the net \(G=(V,E)\) \(\,S\)-\(T\)-flow \(f\: E\to R_+\), allows to construct the flow expansion into the sum \(S\times T\) of flows between all possible streams of flows for the time \(O(| E| (2+\log(| V| ^2/| E| )))\) (when the powers of sets \(S\) and \(T\) are considered to be fixed). These flows are integral-valued, if the initial flow \(f\) is integral-valued. Reviewer: V. V. Shegai (Tashkent) MSC: 94C05 Analytic circuit theory 68R10 Graph theory (including graph drawing) in computer science 94C15 Applications of graph theory to circuits and networks Keywords:streams of flows; integral-valued flow × Cite Format Result Cite Review PDF