Полиэдральные графы задач РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ и ПОЛНЫЙ ДВУДОЛЬНЫЙ ПОДГРАФ
Аннотация
Приводится эффективное описание графов многогранников задач РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ и ПОЛНЫЙ ДВУДОЛЬНЫЙ ПОДГРАФ. Для каждого из них устанавливается, что плотность графа, то есть его кликовое число, растет экспоненциально по размерности пространства.
Об авторах
Анатолий Игоревич Антонов
Ярославский государственный университет им. П.Г. Демидова
Россия
аспирант
Россия
аспирант
Владимир Александрович Бондаренко
Ярославский государственный университет им. П.Г. Демидова
Россия
д-р физ.-мат. наук, профессор, заведующий кафедрой дискретного анализа
Россия
д-р физ.-мат. наук, профессор, заведующий кафедрой дискретного анализа
Список литературы
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
Просмотров: 544
Послать статью по эл. почте 