Приближенный алгоритм для задачи кластеризации вершин графа с ограниченным числом кластеров

Приближенный алгоритм для задачи кластеризации вершин графа с ограниченным числом кластеров Full article

Journal

Вестник Омского университета
ISSN: 1812-3996

Output data

Year: 2026, Volume: 31, Number: 3, Pages: 4-13 Pages count : 10 DOI: 10.24147/1812-3996.2026.3.4-13

Tags

граф, кластеризация, NP-трудная задача, приближенный алгоритм, гарантированная оценка точности.

Authors

Витютнев Д.Е. ¹ , Ильев В.П. ^2,3

Affiliations

1	ГК «Иннотех», г. Омск, Россия
2	Омский государственный университет им. Ф.М. Достоевского, г. Омск, Россия
3	Институт математики им. С. Л. Соболева СО РАН, Омский филиал, г. Омск, Россия

Funding (1)

Министерство науки и высшего образования РФ

FWNF-2026-0019

В задачах кластеризации вершин графа требуется разбить множество вершин заданного графа на попарно непересекающиеся подмножества (кластеры) таким образом, чтобы минимизировать число ребер между кластерами и число отсутствующих ребер внутри кластеров. Мы рассматриваем вариант задачи, в котором число кластеров ограничено сверху натуральным числом k. Эта задача NP-трудна для любого фиксированного k ⩾ 2. Для этого варианта задачи в случае k = 3 предложен полиномиальный приближенный алгоритм с гарантированной оценкой точности, равной 5.

Витютнев Д.Е. , Ильев В.П.
Приближенный алгоритм для задачи кластеризации вершин графа с ограниченным числом кластеров
Вестник Омского университета. 2026. Т.31. №3. С.4-13. DOI: 10.24147/1812-3996.2026.3.4-13 РИНЦ

Submitted:	Apr 22, 2026
Published online:	Oct 12, 2026

≡ Elibrary:

93432060