УДК 519.8
РОЗРІЗИ В НЕОРІЄНТОВАНИХ ГРАФАХ. IІ
Анотація. Запропоновано два алгоритми перетворення поточної бази поліматроїда до нової з метою поліпшення значення цільової функції.
Вста-новлено еквівалентність задачі максимального розрізу на заданому графі і задачі знаходження мінімального розрізу,
що відокремлює джерело і стік в мережі, побудованої відносно деякої бази розширеного поліматроїда.
Сформульовано необхідні та достатні умови оптимальності розв’язування задачі максимального розрізу
на неорієнтованих графах в термінах теорії потоків.
Ключові слова: графи, розрізи, опукла функція, спеціальні багатогранники, поліматроїд.
ПОВНИЙ ТЕКСТ
Шарифов Фирдовси Ахун-оглы,
доктор физ.-мат. наук, старший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
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.
