Разрезы в неориентированных графах. I / Шарифов Ф. А., Гуляницкий Л. Ф. (2020)
Ukrainian

English  Cybernetics and Systems Analysis   /     Issue (2020, 56 (4))

Sharifov F., Hulianytskyi L.
Cuts in undirected graphs. I

To improve the value of the objective function, two algorithms for transforming the current base into a new one are proposed. It is shown that the maximum cut problem on an undirected graph can be reduced to finding the base of the extended polynomial, for which the value of the minimum cut that separates the source and the sink is maximum. The necessary and sufficient conditions for optimality of the solution of the maximum cut problem on undirected graphs in terms of flow theory are formulated. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: convex function, cuts, graphs, polymatroid, special polyhedra, Computer science, Cybernetics, Flow theories, Maximum cut problems, Minimum cut, Objective functions, Optimality, Undirected graph, Flow graphs


Cite:
Sharifov F., Hulianytskyi L. (2020). Cuts in undirected graphs. I. Cybernetics and Systems Analysis, 56 (4), 46–55. doi: https://doi.org/10.1007/s10559-020-00292-z http://jnas.nbuv.gov.ua/article/UJRN-0001129993 [In Russian].


 

Інститут інформаційних технологій НБУВ


+38 (044) 525-36-24
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна