Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2023, Volume 63, Number 3, Pages 517–530
DOI: https://doi.org/10.31857/S0044466923030079
(Mi zvmmf11531)
 

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
English version:
Computational Mathematics and Mathematical Physics, 2023, Volume 63, Issue 3, Pages 491–503
DOI: https://doi.org/10.1134/S0965542523030077
Bibliographic databases:
Document Type: Article
UDC: 519.86
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Kar23}
\by A.~V.~Karzanov
\paper On stable flows and preflows
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2023
\vol 63
\issue 3
\pages 517--530
\mathnet{http://mi.mathnet.ru/zvmmf11531}
\crossref{https://doi.org/10.31857/S0044466923030079}
\elib{https://elibrary.ru/item.asp?id=50435768}
\transl
\jour Comput. Math. Math. Phys.
\yr 2023
\vol 63
\issue 3
\pages 491--503
\crossref{https://doi.org/10.1134/S0965542523030077}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf11531
  • https://www.mathnet.ru/eng/zvmmf/v63/i3/p517
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Statistics & downloads:
    Abstract page:78
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024