К решению задач о клике как задач с d.c. ограничением
| Авторы: | Т. В. Груздева |
| Аннотация: | Рассматриваются задачи поиска максимальной и максимальной взвешенной клик в неориентированном графе. Приведены новые непрерывные постановки задач о клике в виде задач оптимизации с невыпуклым ограничением. Для их решения применена теория глобального поиска[1], и построены приближенные алгоритмы нахождения максимальной и максимальной взвешенной клик. |
| Ключевые слова: | Максимальная клика, локальный поиск, d.c. программирование, алгоритм глобального поиска |
| УДК: | 519.853.4 |
| Литература: |
1 Стрекаловский А.С. Элементы невыпуклой оптимизации/ А.С.Стрекаловский. — Новосибирск: Наука, 2003. 2 Груздева Т. В. Локальный поиск в задачах с невыпуклыми ограничениями/ Т. В.Груздева, А.С.Стрекаловский // Журн. вычисл. матем. и матем. физ. — 2007. — Т. 47. — № 3. — C. 397–413. 3 ГруздеваТ.В.Решение задачи о клике сведением к задаче сd.c.ограничением/ Т. В. Груздева // Дискретный анализ и исследование операций. — 2008. — Т.15. —№6. —С.20–33. 4 Стрекаловский А. С. Минимизирующие последовательности в задачах с d.c. ограничениями / А. С. Стрекаловский // Журн. вычисл. матем. и матем. физ. — 2005. — Т. 45, № 3. — C. 435–447. |