Preview

Моделирование и анализ информационных систем

Расширенный поиск

Полиэдральные графы задач РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ и ПОЛНЫЙ ДВУДОЛЬНЫЙ ПОДГРАФ

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

Просмотров: 266


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)