Алгоритм приближенного решения задачи о кластерном подграфе Full article
| Conference |
VIII Всероссийская научная конференция «Омские научные чтения», 30 Jan - 28 Feb 2026 , Омск. ОмГУ |
||||||
|---|---|---|---|---|---|---|---|
| Source | Омские научные чтения: Материалы VIII Всероссийской научной конференции. В 2-х частях. Омск, 2026 Compilation, Омский государственный университет им. Ф.М. Достоевского. Омск.2026. 268 c. ISBN 978-5-7779-2758-3. РИНЦ |
||||||
| Output data | Year: 2026, Pages: 24-27 Pages count : 4 | ||||||
| Tags | задача кластеризации; кластерный граф; приближенный алгоритм; гарантированная оценка точности. | ||||||
| Authors |
|
||||||
| Affiliations |
|
Abstract:
В задачах кластеризации на графах требуется для данного графа G найти ближайший к нему кластерный граф на том же множестве вершин, т. е. граф, каждая компонента связности которого является полным графом. В работе рассматривается вариант задачи о кластерном подграфе, в которой размеры кластеров ограничены сверху натуральным числом s. Задача является NP-трудной для любого фиксированного значения s 3. Для этой задачи предложен приближенный алгоритм, доказана гарантированная оценка его точности.
Cite:
Ильев А.В.
, Ильев В.П.
Алгоритм приближенного решения задачи о кластерном подграфе
In compilation Омские научные чтения: Материалы VIII Всероссийской научной конференции. В 2-х частях. Омск, 2026. – Омский государственный университет им. Ф.М. Достоевского., 2026. – Т.Часть 1. – C.24-27. – ISBN 978-5-7779-2758-3. РИНЦ
Алгоритм приближенного решения задачи о кластерном подграфе
In compilation Омские научные чтения: Материалы VIII Всероссийской научной конференции. В 2-х частях. Омск, 2026. – Омский государственный университет им. Ф.М. Достоевского., 2026. – Т.Часть 1. – C.24-27. – ISBN 978-5-7779-2758-3. РИНЦ
Identifiers:
| ≡ Elibrary: | 89085496 |