|
Computer science
On stable flows and preflows
A. V. Karzanov Central Institute of Economics and Mathematics, Russian Academy of Sciences, 117418, Moscow, Russia
Abstract:
We propose a new algorithm of finding a stable flow in a network with several sources and sinks. It is based on the idea of preflows (applied in the 1970s for a faster solution of the classical maximal flow problem) and has time complexity $O(nm)$ for a network with $n$ vertices and $m$ edges. The obtained results are further generalized to a larger class of objects, the so-called stable quasi-flows with bounded deviations from the balanced relations in nonterminal vertices.
Key words:
stable flow in a network, stable allocation, preflow, quasi-flow.
Received: 11.08.2022 Revised: 26.08.2022 Accepted: 17.11.2022
Citation:
A. V. Karzanov, “On stable flows and preflows”, Zh. Vychisl. Mat. Mat. Fiz., 63:3 (2023), 517–530; Comput. Math. Math. Phys., 63:3 (2023), 491–503
Linking options:
https://www.mathnet.ru/eng/zvmmf11531 https://www.mathnet.ru/eng/zvmmf/v63/i3/p517
|
Statistics & downloads: |
Abstract page: | 78 |
|