Том 15, номер 6, 2008 г., Стр. 20-33

УДК 519.853.4
Т. В. Груздева
Решение задачи о клике сведением к задаче с d.c. ограничением

Аннотация:
Рассматриваются задачи поиска максимальной и максимальной взвешенной клик в неориентированном графе. Приведены новые непрерывные постановки задач о клике в виде задач оптимизации с невыпуклым ограничением. Для их решения применена стратегия глобального поиска [4–6], основными этапами которой являются локальный поиск, построение аппроксимаций поверхности уровня и решение линеаризованных задач. На её основе построены приближённые алгоритмы нахождения максимальной и максимальной взвешенной клик. Представлены основные этапы реализации алгоритмов, и приведено численное сравнение с другими методами решения задач о клике.

Ключевые слова: максимальная клика, локальный поиск, d.c. программирование, стратегия глобального поиска.

Груздева Татьяна Владимировна ¹
1. Институт динамики систем и теории управления СО РАН,
ул. Лермонтова, 134, 664033 Иркутск, Россия
е-mail: gruzdeva@icc.ru

Статья поступила 14 июля 2008 г.
Исправленный вариант — 20 августа 2008 г.