电邮这篇文章 On Stable Flows and Preflows
- 作者: Karzanov A.V.1
-
隶属关系:
- Central Institute of Economics and Mathematics, Russian Academy of Sciences
- 期: 卷 63, 编号 3 (2023)
- 页面: 517-530
- 栏目: Computer science
- URL: https://journals.rcsi.science/0044-4669/article/view/134310
- DOI: https://doi.org/10.31857/S0044466923030079
- EDN: https://elibrary.ru/EBUSXU
- ID: 134310
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
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.
作者简介
A. Karzanov
Central Institute of Economics and Mathematics, Russian Academy of Sciences
编辑信件的主要联系方式.
Email: akarzanov7@gmail.com
117418, Moscow, Russia
参考
- 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.
补充文件
