Алгоритм приближенного решения задачи о кластерном подграфе Научная публикация
| Конференция |
VIII Всероссийская научная конференция «Омские научные чтения», 30 янв. - 28 февр. 2026 , Омск. ОмГУ |
||||||
|---|---|---|---|---|---|---|---|
| Сборник | Омские научные чтения: Материалы VIII Всероссийской научной конференции. В 2-х частях. Омск, 2026 Сборник, Омский государственный университет им. Ф.М. Достоевского. Омск.2026. 268 c. ISBN 978-5-7779-2758-3. РИНЦ |
||||||
| Вых. Данные | Год: 2026, Страницы: 24-27 Страниц : 4 | ||||||
| Ключевые слова | задача кластеризации; кластерный граф; приближенный алгоритм; гарантированная оценка точности. | ||||||
| Авторы |
|
||||||
| Организации |
|
Реферат:
В задачах кластеризации на графах требуется для данного графа G найти ближайший к нему кластерный граф на том же множестве вершин, т. е. граф, каждая компонента связности которого является полным графом. В работе рассматривается вариант задачи о кластерном подграфе, в которой размеры кластеров ограничены сверху натуральным числом s. Задача является NP-трудной для любого фиксированного значения s 3. Для этой задачи предложен приближенный алгоритм, доказана гарантированная оценка его точности.
Библиографическая ссылка:
Ильев А.В.
, Ильев В.П.
Алгоритм приближенного решения задачи о кластерном подграфе
В сборнике Омские научные чтения: Материалы VIII Всероссийской научной конференции. В 2-х частях. Омск, 2026. – Омский государственный университет им. Ф.М. Достоевского., 2026. – Т.Часть 1. – C.24-27. – ISBN 978-5-7779-2758-3. РИНЦ
Алгоритм приближенного решения задачи о кластерном подграфе
В сборнике Омские научные чтения: Материалы VIII Всероссийской научной конференции. В 2-х частях. Омск, 2026. – Омский государственный университет им. Ф.М. Достоевского., 2026. – Т.Часть 1. – C.24-27. – ISBN 978-5-7779-2758-3. РИНЦ
Идентификаторы БД:
| ≡ РИНЦ: | 89085496 |