Том 21, номер 3, 2014 г., Стр. 82-86

УДК 519.852.2
Селиверстов А. В.
Многогранники и связные подграфы

Аннотация:
Дано описание рёбер релаксационных многогранников для булева квадратичного программирования. Установлено соответствие между инцидентными целой вершине рёбрами такого многогранника и связными подграфами полного графа. 
Табл. 1, библиогр. 12.

Ключевые слова: комбинаторная оптимизация, полиэдральный конус, многогранник, подграф.

Селиверстов Александр Владиславович ¹
1. Институт проблем передачи информации им. А. А. Харкевича РАН,
Большой Каретный пер., 19, 127994 Москва, Россия
е-mail: slvstv@iitp.ru

Статья поступила 22 августа 2013 г.
Исправленный вариант — 17 февраля 2014 г.

Литература

[1] Арутюнов А. В. Две задачи теории квадратичных отображений // Функцион. анализ и его прил. - 2012. - Т. 46, №3. - С. 81–84.
Arutyunov A. V. Two problems of the theory of quadratic maps // Funct. Anal. Appl. - 2012. - Vol. 46, N3. - P. 225–227.

[2] Владимиров А. А. Паросочетания без пересечений // Пробл. передачи информ. - 2013. - Т. 49, №1. - С. 61–65.
Vladimirov A. A. Non-crossing matchings // Probl. Inf. Transmission. - 2013. - Vol. 49, N1. - P. 54–57.

[3] Воблый В. А. Об одной формуле для числа помеченных связных графов // Дискрет. анализ и исслед. операций. - 2012. - Т. 19, №4. - С. 48–59.

[4] Горбунов К. Ю., Любецкий В. А. Дерево, ближайшее в среднем к данному набору деревьев // Пробл. передачи информ. - 2011. - Т. 47, №3. - С. 64–79.
Gorbunov K. Yu., Lyubetsky V. A. The tree nearest on average to a given set of trees // Probl. Inf. Transmission. - 2011. - Vol. 47, N3. - P. 274–288.

[5] Горбунов К. Ю., Селиверстов А. В., Любецкий В. А. Взаимное расположение параллельных гиперплоскостей, квадрик и вершин многомерного куба // Пробл. передачи информ. - 2012. - Т. 48, №2. - C. 113–120.
Gorbunov K. Yu., Seliverstov A. V., Lyubetsky V. A. Geometric relationship between parallel hyperplanes, quadrics, and vertices of a hypercube // Prob. Inf. Transmission. - 2012. - Vol. 48, N2. - P. 185–192.

[6] Ерзин А. И., Плотников Р. В., Шамардин Ю. В. О некоторых полиномиально разрешимых случаях и приближённых алгоритмах для задачи построения оптимального коммуникационного дерева // Дискрет. анализ и исслед. операций. - 2013. - Т. 20, №1. - С. 12–27.
Erzin A. I., Plotnikov R. V., Shamardin Yu. V. On some polynomially solvable cases and approximate algorithms in the optimal communication tree construction problem // J. Appl. Industr. Math. - 2013. - Vol. 7, N2. - P. 142–152.

[7] Максименко А. Н. k-Смежностные грани булева квадратичного многогранника // Фундамент. и прикл. математика. - 2013. - Т. 18, №2. - С. 95–103.

[8] Селиверстов А. В. О мономах квадратичных форм // Дискрет. анализ и исслед. операций. - 2013. - Т. 20, №3. - С. 65–70.
Seliverstov A. V. Monomials in quadratic forms // J. Appl. Industr. Math. - 2013. - Vol. 7, N3. - P. 431–434.

[9] Стецюк П. И., Золотых Н. Ю. Бинарный квадратичный многогранник и его аппроксимации // Журн. обчисл. та прикл. математики. - 2010. - №2. - С. 139–149.

[10] Шлык В. А. О вершинах главного многогранника Гомори // Докл. НАН Беларуси. - 2011. - Т. 55, №5. - С. 14–17.

[11] Шлык В. А. Опорные вершины главного многогранника Гомори // Вестн. Белорус. гос. ун-та. Сер. 1. Физика. Математика. Информатика. - 2012. - №1. - С. 49–54.

[12] Avis D., Fukuda K. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra // Discrete Сomput. Geom. - 1992. - Vol. 8, N1. - P. 295–313.

[13] Conrad J. M., Gomes C. P., van Hoeve W.-J., Sabharwal A., Suter J. F. Wildlife corridors as a connected subgraph problem // J. Environ. Econ. Manage. - 2012. - Vol. 63, N1. - P. 1–18.

[14] Padberg M. The boolean quadric polytope: some characteristics, facets and relatives // Math. Program. - 1989. - Vol. 45, N1–3. - P. 139–172.