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