УДК 519.8
РАЗРЕЗЫ В НЕОРИЕНТИРОВАННЫХ ГРАФАХ. II
Аннотация. Предложены два алгоритма преобразования текущей базы по-лиматроида в новую для улучшения значения целевой функции.
Установле-на эквивалентность задачи максимального разреза на заданном графе и за-дачи нахождения минимального разреза,
отделяющего источник и сток в сети, построенной относительно некоторой базы расширенного полимат-роида.
Сформулированы необходимые и достаточные условия оптимальнос-ти решения задачи максимального разреза
на неориентированных графах в терминах теории потоков.
Ключевые слова: графы, разрезы, выпуклая функция, специальные многогранники, полиматроид.
ПОЛНЫЙ ТЕКСТ
Шарифов Фирдовси Ахун-оглы,
доктор физ.-мат. наук, старший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
fasharifov@gmail.com
Гуляницкий Леонид Федорович,
доктор техн. наук, заведующий отделом Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
lh_dar@hotmail.com
СПИСОК ЛИТЕРАТУРЫ
- Шарифов Ф.А., Гуляницкий Л.Ф. Разрезы в неориентированных графах. I. Кибернетика и системный анализ. 2020. Т. 56, № 4. С. 46–55.
- Bazaraa M.S., Sherali H.D., Shetty M.C. Nonlinear programming: Theory and algorithms. New York: J. Wiley and Sons, 1979. 583 p.
- Satoru Iwata. Submodular function minimization. Math. Program. Ser. B. 2008. Vol. 112. P. 45–64.
- Шарифов Ф.А. Нахождения максимального разреза гриди алгоритмом. Кибернетика и системный анализ. 2018. Т. 54, № 5. С. 61–67.
- Fujishige S. Submodular function and optimization. Annals of Discrete Mathematics. 2005. Р. 395.
- Rothvoss T. The matching polytope has exponential extension complexity. ACM Symposium on the Theory of Computing. 2014. P. 263–272.
- Queyranne M. A combinatorial algorithm for minimizing symmetric submodular function. Math. Prog. Ser. A. 1998. Vol. 82. Р. 3–12.
- Rendl F., Giovanni R., Wiegele A. Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Mathematical Programming. 2010. Vol. 121, Iss. 2. P. 307.
