О генерической сложности ограниченной проблемы кластеризации графов Научная публикация
| Журнал |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||
|---|---|---|---|
| Вых. Данные | Год: 2022, Номер: 57, Страницы: 91–97 Страниц : 8 DOI: 10.17223/20710410/57/6 | ||
| Ключевые слова | генерическая сложность, кластеризация графа | ||
| Авторы |
|
||
| Организации |
|
Информация о финансировании (1)
| 1 | Российский научный фонд | 22-11-20019 |
Реферат:
Изучается генерическая сложность проблемы кластеризации графов с ограничениями на число кластеров. В этой проблеме структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на ограниченное число попарно непересекающихся групп (кластеров) так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Строится подпроблема этой проблемы, для которой, при условии P ≠ NP и P = BPP, не существует полиномиального генерического алгоритма.
Библиографическая ссылка:
Рыбалов А.Н.
О генерической сложности ограниченной проблемы кластеризации графов
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. №57. С.91–97. DOI: 10.17223/20710410/57/6 WOS Scopus РИНЦ OpenAlex
О генерической сложности ограниченной проблемы кластеризации графов
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2022. №57. С.91–97. DOI: 10.17223/20710410/57/6 WOS Scopus РИНЦ OpenAlex
Идентификаторы БД:
| Web of science: | WOS:000870532200006 |
| Scopus: | 2-s2.0-85148856878 |
| РИНЦ: | 49454228 |
| OpenAlex: | W4312989877 |