|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)
О задаче кластеризации графа с ограничением на размеры кластеров
В. П. Ильевab, С. Д. Ильеваb, А. А. Навроцкаяab a Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Омский гос. университет им. Ф. М. Достоевского, пр. Мира, 55-А, 644077 Омск, Россия
Аннотация:
Изучается версия задачи кластеризации графа (известной также как задача аппроксимации графа), в которой размеры кластеров ограничены сверху заданным числом $p$. Для этой задачи предложен новый приближённый алгоритм с достижимой гарантированной оценкой точности. Тем самым показано, что задача кластеризации графа с ограничением на размеры кластеров принадлежит классу $APX$ для любого фиксированного $p$. Ил. 2, библиогр. 20.
Ключевые слова:
кластеризация, аппроксимация, граф, приближённый алгоритм, гарантированная оценка точности.
Статья поступила: 28.12.2015 Переработанный вариант: 28.03.2016
Образец цитирования:
В. П. Ильев, С. Д. Ильева, А. А. Навроцкая, “О задаче кластеризации графа с ограничением на размеры кластеров”, Дискретн. анализ и исслед. опер., 23:3 (2016), 5–20; J. Appl. Industr. Math., 10:3 (2016), 341–348
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da849 https://www.mathnet.ru/rus/da/v23/i3/p5
|
Статистика просмотров: |
Страница аннотации: | 259 | PDF полного текста: | 187 | Список литературы: | 36 | Первая страница: | 3 |
|