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

Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай

Результат исследований: Вклад в журналСтатья

Аннотация

Рассматривается задача поиска фиксированного числа вершинно-несмежных клик заданных размеров в полном неориентированном взвешенном графе по критерию минимума суммарного веса вершин и ребер в найденных кликах. Показано, что задача -трудна в сильном смысле как общем случае, так и в двух частных постановках, обладающих важными приложениями. Представлен приближенный алгоритм решения задачи. Показано, что для рассмотренных подклассов задачи алгоритм находит решение с гарантированной оценкой точности, причем в обоих случаях оценка достижима. В случае, когда число искомых клик фиксировано заранее (т.е. не входит в условие задачи), временная сложность предложенного алгоритма полиномиальна.
Переведенное название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 МАТЕМАТИКА

Уровень публикации

  • Перечень ВАК

Fingerprint Подробные сведения о темах исследования «ЭФФЕКТИВНЫЕ АЛГОРИТМЫ С ОЦЕНКАМИ ТОЧНОСТИ ДЛЯ НЕКОТОРЫХ ЗАДАЧ ПОИСКА НЕСКОЛЬКИХ КЛИК В ПОЛНОМ НЕОРИЕНТИРОВАННОМ ВЗВЕШЕННОМ ГРАФЕ». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать