А. В. Ильев, В. П. Ильев, “Об одной задаче кластеризации графа с частичным обучением”, ПДМ, 2018, номер 42,страницы 66

Эта публикация цитируется в 3 статьях

Прикладная теория графов

Об одной задаче кластеризации графа с частичным обучением

А. В. Ильев^ab, В. П. Ильев^ac

^a Омский государственный технический университет, г. Омск, Россия,
^b Институт математики им. С.Л. Соболева СО РАН, г. Омск, Россия,
^c Омский государственный университет им. Ф.М. Достоевского, г. Омск, Россия

Аннотация: В задачах кластеризации требуется разбить данное множество объектов на несколько подмножеств (кластеров) только на основе сходства объектов друг с другом. Рассматривается вариант задачи кластеризации графа, являющийся одной из формализаций задачи кластеризации с частичным обучением. Доказано, что эта задача является NP-трудной. Для одного варианта задачи предложен полиномиальный 3-приближённый алгоритм.

Ключевые слова: граф, кластер, кластеризация с частичным обучением.

УДК: 519.1

DOI: 10.17223/20710410/42/5