Email this article On Stable Flows and Preflows
- Authors: Karzanov A.V.1
-
Affiliations:
- Central Institute of Economics and Mathematics, Russian Academy of Sciences
- Issue: Vol 63, No 3 (2023)
- Pages: 517-530
- Section: ИНФОРМАТИКА
- URL: https://journals.rcsi.science/0044-4669/article/view/134310
- DOI: https://doi.org/10.31857/S0044466923030079
- EDN: https://elibrary.ru/EBUSXU
- ID: 134310
Cite item
Open Access
Access granted
Subscription Access
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 for a network with O(nm) 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.
Keywords
About the authors
A. V. Karzanov
Central Institute of Economics and Mathematics, Russian Academy of Sciences
Author for correspondence.
Email: akarzanov7@gmail.com
117418, Moscow, Russia
References
- Gale D., Shapley L.S. College admissions and the stability of marriage // Amer. Math. Monthly. 1962. V. 69. № 1. P. 9–15.
- Irving R.W. An efficient algorithm for the “stable roommates” problem // J. Algorithms. 1985. V. 6. P. 577–595.
- Tan J. A necessary and sufficient condition for the existence of a complete stable matching // J. Algorithms. 1991. V. 12. P. 154–178.
- Baiou M., Balinski M. Erratum: the stable allocation (or ordinal transportation) problem // Math. Oper. Res. 2002. V. 27. № 4. P. 662–680.
- Dean B.C., Munshi S. Faster algorithms for stable allocation problems // Algorithmica. 2010. V. 58. № 1. P. 59–81.
- Sleator D.D., Tarjan R.E. A data structure for dynamic trees // J. Computer and System Sciences. 1983. V. 26. № 3. P. 362–391.
- Sleator D.D., Tarjan R.E. Self-adjusting binary search trees // J. ACM. 1985. V. 32. № 3. P. 652–686.
- Fleiner T. On stable matchings and flows // Algorithms. 2014. V. 7. P. 1–14.
- Ostrovsky M. Stability in supply chain networks // Amer. Econ. Rev. 2006. V. 98. P. 897–923.
- Cseh Á., Matuschke J. New and simple algorithms for stable flow problems // Algorithmica. 2019. V. 81. № 6. P. 2557–2591.
- Карзанов А.В. Нахождение максимального потока в сети методом предпотоков // Докл. АН СССР. 1974. Т. 215. С. 49–52. (English translation in: Soviet Math. Dokl. 1974. V. 15. № 2. P. 434–437.)
- Cseh Á., Matuschke J., Skutella M. Stable flows over time // Algorithms. 2013. V. 6. P. 532–545.
