Послать статью по эл. почте 
Устойчивость в задаче поиска минимального разреза в графе
https://doi.org/10.18255/1818-1015-2014-4-54-63
Аннотация
Об авторе
Илья Владимирович КозловРоссия
кафедра математических основ управления аспирант, ассистент, 141700, Московская облаcть, г. Долгопрудный, Институтский пер., 9
Список литературы
1. Bilu Y., Linial N. Are stable instances easy? // Innov. in Comp. Sci. 2010. P. 332–341.
2. Linial N. et.al. On the practically interesting instances of MAXCUT // STACS. 2013. P. 526–537.
3. Makarychev K., Makarychev Y., Vijayaraghavan A. Bulu-Linial stable instances of max cut and minimum multiway cut // Proc. of the 25-th ACM-SIAM Symp. on Disc. Alg. 2014. P. 890–906. DOI: 10.1137/1.9781611973402.67
4. Ford L., Fulkerson D. Maximal flow through a network // Canadian Journal of Mathematics. 1956. № 8. P. 399–404.
5. Gomory R., Hu T. Multi-terminal network flows // Journal of the Society of Industrial and Applied Mathematics. Dec.1961. P. 551–570.
6. Hao J., Orlin J. A faster algorithm for finding the minimum cut in a directed graph // Journal of Algorithms. Nov.1994. Vol. 17, № 3. P. 424–446.
7. Карзанов А.В., Тимофеев Е.А. Эффективный алгоритм нахождения всех минимальных реберных разрезов неориентированного графа // Кибернетика. 1986. № 2. С. 8–12. (English transl.: Karzanov A.V., Timofeev E.A. Efficient algorithm for finding all minimal edge cuts of a nonoriented graph // Kibernetika. 1986. № 2. P. 8–12.)
8. Поддерюгин В.Д. Алгоритм для нахождения реберной связности графа // Вопросы кибернетики. 1973. № 2. С. 136. (English transl.: Podderyugin V.D. An algorithm for finding the edge connectivity of graphs // Vopr. Kibern. 1973. № 2. P. 136.)
9. Karger D., Stein C. A new approach to the minimum cut problem // Journal of the ACM. Jul.1996. Vol. 43, № 4, P. 601–640.
10. Stoer M., Wagner F. A simple min-cut algorithm // Journal of the ACM. Jul. 1997. Vol. 44, № 4. P. 585–591.
11. Леонтьев В.К. Устойчивость задачи коммивояжера // Журн. вычисл. матем. и матем. физ. 1975. Т. 5, № 15. С. 1298–1309. [Leont’ev V.K. Ustoychivost zadachi kommivoyazhera // Zhurn. vychisl. matem. i matem. fiz. 1975. Vol. 5, № 15. S. 1298–1309 (in Russian)].
12. Гордеев Э.Н., Леонтьев В.К. Общий подход к исследованию устойчивости решений в задачах дискретной оптимизации // Журн. вычисл. матем. и матем. физ. 1996. Т. 1, № 36. С. 66–72. [Gordeev E.N., Leont’ev V.K. Obshchy podkhod k issledovaniyu ustoychivosti resheny v zadachakh diskretnoy optimizatsii // Zhurn. vychisl. matem. i matem. fiz. 1996. Vol. 1, № 36. S. 66–72. [in Russian].)
13. Orlin J. Max flows in O(nm) time, or better // STOC. 2013. P. 765–774.
14. King V., Rao S., Tarjan R. A Faster Deterministic Maximum Flow Algorithm // Journal of Algorithms. Nov.1994. Vol. 17, № 3. P. 447—474.
Дополнительные файлы
Для цитирования: Козлов И.В. Устойчивость в задаче поиска минимального разреза в графе. Моделирование и анализ информационных систем. 2014;21(4):54-63. https://doi.org/10.18255/1818-1015-2014-4-54-63
For citation: Kozlov I.V. On Stable Instances of MINCUT. Modeling and Analysis of Information Systems. 2014;21(4):54-63. (In Russ.) https://doi.org/10.18255/1818-1015-2014-4-54-63
Обратные ссылки
- Обратные ссылки не определены.
