UDC 519.8
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 fasharifov@gmail.com
|
2 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
lh_dar@hotmail.com
|
CUTS IN UNDIRECTED GRAPHS. IІ
Abstract. To improve the value of the objective function, two algorithms are proposed for transforming
the current base into a new one. 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 non-oriented graphs in terms of flow theory are formulated.
Keywords: graphs, cuts, convex function, special polyhedral, polymatroid.
FULL TEXT
REFERENCES
- Sharifov F.A., Gulyanitskiy L.F. Cuts in undirected graphs. I. Kibernetika i sistemnyj analiz. 2020. Vol. 56, N 4. P. 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.
- Sharifov F.A. Finding the maximum cut using the greedy algorithm. Kibernetika i sistemnyj analiz. 2018. Vol. 54, N 5. P. 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.
