УДК 519.8
РАЗРЕЗЫ В НЕОРИЕНТИРОВАННЫХ ГРАФАХ. I
Аннотация. Исследованы новые свойства разрезов в неориентированных графах, приведены различные модели
для задачи максимального разреза на основе установленного соответствия между разрезами в заданном графе и специфическими
базами расширенного полиматроида, ассоциированного с этим графом.
Для модели, сформулированной как задача нахождения максимума выпуклой функции на компактном множестве — расширенном
по-лиматроиде, доказано, что локальные и глобальные максимумы совпадают по значению целевой функции,
т.е. для решения задачи максимального разреза достаточно найти базу расширенного полиматроида
как локальный или глобальный максимум целевой функции.
Ключевые слова: графы, разрезы, выпуклая функция, специальные мно-гогранники.
ПОЛНЫЙ ТЕКСТ
Шарифов Фирдовси Ахун-оглы,
доктор физ.-мат. наук, старший научный сотрудник Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
fasharifov@gmail.com
Гуляницкий Леонид Федорович,
доктор техн. наук, зав. отделом Института кибернетики им. В.М. Глушкова НАН Украины, Киев,
lh_dar@hotmail.com
СПИСОК ЛИТЕРАТУРЫ
- Barahona F., M., M., Reinelt G. An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research. 1988. Vol. 36, N 3. P. 493–513.
- Karp R.M. Reducibility among combinatorial problems. Miller R.E., Thatcher J.W., Bohlinger J.D. (Eds.). Complexity of Computer Computations. New York: Plenum Press, 1972. P. 85–103.
- Garey M.R., Johnson D.S., Stockmeyer L. Some simplified -complete graph problems. Theoret. Comput. Sci. 1976. Vol. 1, Iss. 3. P. 237–267.
- Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of -completeness. New York: W.H. Freeman and Company, 1979.
- Boros E., Hammer P.L. Pseudo-Boolean optimization. Discrete Applied. Mathematics. 2002. Vol. 123, Iss. 1–3. P. 155–225.
- Bertoni A., Campadelli P., Grossi G. An approximation algorithm for the maximum cut problem and its experimental analysis. Discrete Applied Mathematics. 2001. Vol. 110, Iss. 1. P. 3–12.
- Orlova G.I., Dorfman Y.G. Finding the maximal cut in a graph. Engineering Cybernetics. 1972. Vol. 10. P. 502–504.
- Hadlock F.O. Finding a maximum cut of a planar graph in polynomial time. SIAM Journal on Computing. 1975. Vol. 4, Iss. 3. P. 221–225.
- Shih K., Wu S., Kuo Y.S. Unifying maximum cut and minimum cut of a planar graph. IEEE Transactions on Computers. 1990. Vol. 39, Iss. 5. P. 694–697.
- Grotschel M., Pulleyblank W.R. Weakly bipartite graphs and the max-cut problem. Operat. Res. Lett. 1981. Vol. 1, Iss. 1. P. 23–27.
- Barahona F. The max-cut problem in graphs is not contractible to K5 Operat. Res. Lett. 1983. Vol. 2, Iss. 3. P. 107–111.
- Brahim Chaourar. A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs. 2017. Vol. 2017. Article ID 1267108. 4 p. https://doi.org/10.1155/2017/1267108.
- Ben-Ameur W., Mahjoub A.R., Neto J. The maximum cut problem. In: Paradigms of combinatorial optimization. In Problems and New Approaches. Ch. 6. Paschos V.T. (Ed.). J. Wiley and Sons, USA, 2nd edition, 2014.
- Poljak S., Tuza Z. Maximum cuts and large bipartite subgraphs. American Mathematical Society. 1995. Vol. 20. P. 181–244.
- Goemans M.X., Williamson D.P. Improved approximation algorithms for MAX-CUT and satisfiability problems using semidefinite programming. Journal of ACM. 1995. Vol. 42, N 6. P. 1115–1145.
- Rendl F., Rinaldi G., Wiegele A. Solving MAX-CUT to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. Publ. Online: May 6, 2008. 33 p. URL:
- Шарифов Ф.А. Нахождения максимального разреза гриди алгоритмом. Кибернетика и системный анализ. 2018. Т. 54, № 5. C. 48–54.
- Stoer M., Wagner F. A simple min cut algorithm. Journal of ACM. 1997. Vol. 44, N 4. P. 583–591.
- Iwata S. Submodular function minimization. Math. Program. Ser. A–B. 2008. Vol. 112, N 1. P. 45–64.
- Bazaraa M.S., Sherali H.D., Shetty M.C. Nonlinear programming: Theory and algorithms. New York: J. Wiley and Sons, 1979. 583 p.
