|
Труды Института математики и механики УрО РАН, 2014, том 20, номер 2, страницы 99–112
(Mi timm1062)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе
Э. Х. Гимадиab, А. В. Кельмановba, А. В. Пяткинab, М. Ю. Хачайcd a Институт математики СО РАН
b Новосибирский государственный университет
c Уральский федеральный университет им. Б. Н. Ельцина
d Институт математики и механики им. Н. Н. Красовского УрО РАН
Аннотация:
Рассматривается задача поиска фиксированного числа вершинно-несмежных клик заданных размеров в полном неориентированном взвешенном графе по критерию минимума суммарного веса вершин и ребер в найденных кликах. Показано, что задача $NP$-трудна в сильном смысле как общем случае, так и в двух частных постановках, обладающих важными приложениями. Представлен приближенный алгоритм решения задачи. Показано, что для рассмотренных подклассов задачи алгоритм находит решение с гарантированной оценкой точности, причем в обоих случаях оценка достижима. В случае, когда число искомых клик фиксировано заранее (т.е. не входит в условие задачи), временная сложность предложенного алгоритма полиномиальна.
Ключевые слова:
поиск вершинно-несмежных клик, минимум суммарного веса вершин и ребер, приближенный алгоритм, гарантированная точность, достижимость оценок, метрическая задача, квадратичная евклидова задача.
Поступила в редакцию: 30.01.2014
Образец цитирования:
Э. Х. Гимади, А. В. Кельманов, А. В. Пяткин, М. Ю. Хачай, “Эффективные алгоритмы с оценками точности для некоторых задач поиска нескольких клик в полном неориентированном взвешенном графе”, Тр. ИММ УрО РАН, 20, № 2, 2014, 99–112; Proc. Steklov Inst. Math. (Suppl.), 289, suppl. 1 (2015), 88–101
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/timm1062 https://www.mathnet.ru/rus/timm/v20/i2/p99
|
Статистика просмотров: |
Страница аннотации: | 367 | PDF полного текста: | 81 | Список литературы: | 57 | Первая страница: | 16 |
|