name: Некоторые наследственные случаи полиномиальной и псевдополиномиальной разрешимости задач о вершинной раскраске графов
keyword_list: алгоритмическая теория графов раскраска вычислительная сложность
abstract: В работе предложены новые методы для построения полиномиальных и псевдополиномиальных алгоритмов решения подзадач задачи о взвешенной вершинной раскраске; доказана полиномиальная разрешимость задачи о вершинной раскраске для графов, одновременно не содержащих порожденного пути с 5 вершинами и порожденной клики с удаленным ребром; доказана псевдополиномиальная разрешимость задачи о взвешенной вершинной раскраске для графов, одновременно не содержащих порожденного пути с 5 вершинами и порожденного подграфа, получающегося добавлением вершины к циклу с 4 вершинами и ребер, инцидентных добавленной вершине и трем вершинам цикла; доказана псевдополиномиальная разрешимость задачи о взвешенной вершинной раскраске для графов, одновременно не содержащих порожденного пути с 5 вершинами, порожденного полного двудольного графа с 2 вершинами в одной доле и 3 вершинами в другой доле и порожденного полного трехдольного графа с долями, состоящими из 1,1 и 3 вершин.
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: A-4743-2017
chairman_dissertation_council.scopus_author_id: 7006796582
chairman_dissertation_council.territory: РОССИЯ
organization_supervisor.name: Михаил
organization_supervisor.surname: Иванченко
organization_supervisor.patronymic: Васильевич
organization_supervisor.position: Проректор по научной работе
organization_supervisor.territory: РОССИЯ
rubrics.code: 27.45.17
rubrics.name: Теория графов
oecds.code: 01.01.PQ
oecds.name: MATHEMATICS
speciality_codes.name: Дискретная математика и математическая кибернетика
speciality_codes.code: 01.01.09
supervisors.fio: Малышев Д.С,
supervisors.scientific_degree: Доктор физико-математических наук
supervisors.speciality_code: Дискретная математика и математическая кибернетика
supervisors.responsible_type: Научный руководитель
opponents.fio: Абросимов М.Б.
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: 1025203733510
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: 1027739630401
author_organization.supervisor_name: ЯРОСЛАВ
author_organization.supervisor_surname: КУЗЬМИНОВ
author_organization.supervisor_patronymic: ИВАНОВИЧ
author_organization.organization_type: Организация
author_organization.okogu: Правительство Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения