Полиэдральные графы задач РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ и ПОЛНЫЙ ДВУДОЛЬНЫЙ ПОДГРАФ
Аннотация
Приводится эффективное описание графов многогранников задач РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ и ПОЛНЫЙ ДВУДОЛЬНЫЙ ПОДГРАФ. Для каждого из них устанавливается, что плотность графа, то есть его кликовое число, растет экспоненциально по размерности пространства.
Об авторах
Анатолий Игоревич АнтоновРоссия
аспирант
Владимир Александрович Бондаренко
Россия
д-р физ.-мат. наук, профессор, заведующий кафедрой дискретного анализа
Список литературы
1. Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.
2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
Рецензия
Для цитирования:
Антонов А.И., Бондаренко В.А. Полиэдральные графы задач РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ и ПОЛНЫЙ ДВУДОЛЬНЫЙ ПОДГРАФ. Моделирование и анализ информационных систем. 2012;19(6):101-106. https://doi.org/10.18255/1818-1015-2012-6-101-106
For citation:
Antonov A.I., Bondarenko V.A. Polyhedral Graphs of GRAPH PARTITIONING and COMPLETE BIPARTITE SUBGRAPH Problems. Modeling and Analysis of Information Systems. 2012;19(6):101-106. (In Russ.) https://doi.org/10.18255/1818-1015-2012-6-101-106