name: Исследование вычислительной сложности задач о независимом множестве и о вершинной k-раскраске в некоторых классах графов
keyword_list: ЗАДАЧА О НЕЗАВИСИМОМ МНОЖЕСТВЕ, ЗАДАЧА О 3-РАСКРАСКЕ, ЛОКАЛЬНОЕ ПРЕОБРАЗОВАНИЕ
abstract: Вводятся и развиваются методы построения полиномиальных алгоритмов и полиномиальных сведений для задач о независимом множестве и о вершинной k-раскраске. Данные методы применяются для анализа вычислительной сложности актуальных подзадач данных задач. Устанавливается сложностной статус задачи о независимом множестве в некоторых подмножествах множества планарных графов, сложностной статус задачи о вершинной 3-раскраске в некоторых подклассах класса планарных графов и в некоторых наследственных классах, определяемых небольшими запрещенными порожденными структурами.
chairman_dissertation_council.surname: Стронгин Р. Г.
chairman_dissertation_council.position: президент ННГУ, заведующий кафедрой, профессор
chairman_dissertation_council.degree: Доктор физико-математических наук
organization_supervisor.surname: Марков К.А.
organization_supervisor.position: Первый проректор
organization_supervisor.degree: Кандидат физико-математических наук
rubrics.code: 27.45.17
rubrics.name: Теория графов
oecds.code: 01.01.00
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.organization_type: Организация
protection_organization.okogu: Министерство науки и высшего образования Российской Федерации
protection_organization.okopf: Федеральные государственные автономные учреждения
author_organization.short_name: Национальный исследовательский университет "Высшая школа экономики"; Национальный исследовательский университет ВШЭ; Высшая школа экономики; НИУ ВШЭ; ВШЭ
author_organization.name: Федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Высшая школа экономики"
author_organization.ogrn: 1027739630401
author_organization.organization_type: Организация
author_organization.okogu: Правительство Российской Федерации
author_organization.okopf: Федеральные государственные автономные учреждения