О сложности кластеризации графа в задаче с ограничениями на размеры кластеров Р. В. Балджанова, А. В. Ильев, В. П. Ильев
Material type:
ArticleContent type: Текст Media type: электронный Other title: On the complexity of graph clustering in the problem with bounded cluster sizes [Parallel title]Subject(s): графы | кластеризация графов | сложность кластеризацииGenre/Form: статьи в журналах Online resources: Click here to access online
In:
Прикладная дискретная математика № 60. С. 76-84Abstract: В задачах кластеризации на графах для данного графа G требуется найти ближайший к нему кластерный граф на том же множестве вершин. Граф называется кластерным, если каждая его компонента связности является полным графом. Расстояние между двумя графами понимается как число несовпадающих рёбер. Рассматривается задача кластеризации на графах, в которой размеры кластеров ограничены сверху числом s. Доказана верхняя оценка сложности кластеризации произвольного графа для случая s = 2. Предложен приближённый полиномиальный алгоритм решения задачи кластеризации на графах для случая s = 3 и доказана верхняя оценка сложности кластеризации произвольного графа для этого случая.
Библиогр.: 12 назв.
В задачах кластеризации на графах для данного графа G требуется найти ближайший к нему кластерный граф на том же множестве вершин. Граф называется кластерным, если каждая его компонента связности является полным графом. Расстояние между двумя графами понимается как число несовпадающих рёбер. Рассматривается задача кластеризации на графах, в которой размеры кластеров ограничены сверху числом s. Доказана верхняя оценка сложности кластеризации произвольного графа для случая s = 2. Предложен приближённый полиномиальный алгоритм решения задачи кластеризации на графах для случая s = 3 и доказана верхняя оценка сложности кластеризации произвольного графа для этого случая.
There are no comments on this title.