ЭФФЕКТИВНЫЕ АЛГОРИТМЫ С ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ НЕКОТОРЫХ ЗАДАЧ ПОИСКА НЕСКОЛЬКИХ КЛИК В ПОЛНОМ НЕОРИЕНТИРОВАННОМ ВЗВЕШЕННОМ ГРАФЕ

Рассматривается задача поиска фиксированного числа вершинно-несмежных клик заданных размеров в полном неориентированном взвешенном графе по критерию минимума суммарного веса вершин и ребер в найденных кликах. Показано, что задача -трудна в сильном смысле как общем случае, так и в двух частных постановках, обладающих важными приложениями. Представлен приближенный алгоритм решения задачи. Показано, что для рассмотренных подклассов задачи алгоритм находит решение с гарантированной оценкой точности, причем в обоих случаях оценка достижима. В случае, когда число искомых клик фиксировано заранее (т.е. не входит в условие задачи), временная сложность предложенного алгоритма полиномиальна.