Аннотация
Рассматривается задача поиска фиксированного числа вершинно-несмежных клик заданных размеров в полном неориентированном взвешенном графе по критерию минимума суммарного веса вершин и ребер в найденных кликах. Показано, что задача -трудна в сильном смысле как общем случае, так и в двух частных постановках, обладающих важными приложениями. Представлен приближенный алгоритм решения задачи. Показано, что для рассмотренных подклассов задачи алгоритм находит решение с гарантированной оценкой точности, причем в обоих случаях оценка достижима. В случае, когда число искомых клик фиксировано заранее (т.е. не входит в условие задачи), временная сложность предложенного алгоритма полиномиальна.
Переведенное название | Efficient algorithms with performance estimates for some problems of finding several cliques in a complete undirected weighted graph |
---|---|
Язык оригинала | Русский |
Страницы (с-по) | 99-112 |
Журнал | Труды института математики и механики УрО РАН |
Том | 20 |
Номер выпуска | 2 |
Состояние | Опубликовано - 2014 |
ГРНТИ
- 27.00.00 МАТЕМАТИКА
Уровень публикации
- Перечень ВАК