name: Приближенное и точное решение различных вариантов задачи кластеризации вершин графа
keyword_list: кластеризация приближенный алгоритм граф гарантированная оценка точности NP-трудная задача
abstract: Объект исследования: труднорешаемые задачи кластеризации вершин графа. Цель работы: построение и анализ приближенных и точных алгоритмов для решения этих задач, их экспериментальное исследование. Основные результаты: представлены приближенные и точные алгоритмы решения различных вариантов задачи кластеризации вершин графа. Предложены приближенные алгоритмы с частичным обучением для нового варианта задачи кластеризации вершин графа, в котором число кластеров равно 2. Получены априорные гарантированные оценки точности приближенных алгоритмов. Для задачи кластеризации вершин графа на два кластера разработана процедура локального поиска. Проведено экспериментальное исследование приближенных и точных алгоритмов. Область применения: в работе получены теоретические и экспериментальные результаты. Результаты могут быть применены в дальнейших исследованиях задач кластеризации, а также для решения практических задач.
chairman_dissertation_council.name: Владимир
chairman_dissertation_council.surname: Береснев
chairman_dissertation_council.patronymic: Леонидович
chairman_dissertation_council.position: зав. лабораторией
chairman_dissertation_council.degree: Доктор физико-математических наук
chairman_dissertation_council.rank: Профессор
chairman_dissertation_council.wos_research_id: 7416422
chairman_dissertation_council.scopus_author_id: 7005979568
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Андрей
organization_supervisor.surname: Миронов
organization_supervisor.patronymic: Евгеньевич
organization_supervisor.position: и.о. директора
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.41.41
rubrics.name: Алгоритмы решения задач вычислительной и дискретной математики
rubrics.code: 27.45.17
rubrics.name: Теория графов
oecds.code: 01.01.PN
oecds.name: MATHEMATICS, APPLIED
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Ильев В.П.
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: Родионов А.C.
opponents.scientific_degree: Доктор технических наук
opponents.speciality_code: Математическое моделирование, численные методы и комплексы программ
opponents.responsible_type: Оппонент
opponents.fio: Мокеев Д.Б.
opponents.scientific_degree: Кандидат физико-математических наук
opponents.speciality_code: Дискретная математика и математическая кибернетика
opponents.responsible_type: Оппонент
protection_organization.short_name: ИМ СО РАН
protection_organization.name: ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ ИМ. С.Л. СОБОЛЕВА СИБИРСКОГО ОТДЕЛЕНИЯ РОССИЙСКОЙ АКАДЕМИИ НАУК
protection_organization.ogrn: 1025403656508
protection_organization.supervisor_name: АНДРЕЙ
protection_organization.supervisor_surname: МИРОНОВ
protection_organization.supervisor_patronymic: ЕВГЕНЬЕВИЧ
protection_organization.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные бюджетные учреждения
author_organization.short_name: ОФ ИМ СО РАН
author_organization.name: Омский филиал Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук
author_organization.ogrn: 1025403656508
author_organization.organization_type: Организация
author_organization.okogu: Министерство науки и высшего образования Российской Федерации
author_organization.okopf: Филиалы юридических лиц