Приближенный алгоритм для задачи кластеризации вершин графа с ограниченным числом кластеров | Sciact - Система учета научной деятельности ИМ СО РАН

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

Журнал

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

Вых. Данные

Год: 2026, Том: 31, Номер: 3, Страницы: 4-13 Страниц : 10 DOI: 10.24147/1812-3996.2026.3.4-13

Ключевые слова

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

Авторы

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

Организации

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

Информация о финансировании (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 РИНЦ

Поступила в редакцию:	22 апр. 2026 г.
Опубликована online:	12 окт. 2026 г.

≡ РИНЦ:

93432060