30 июня 2020, Заседание научного семинара лаборатории

16:00 - 17:30, Zoom

Тема: Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторых наследственных классов графов
Докладчик: Развенская О.О. (НИУ ВШЭ)

Аннотация: В докладе рассматривается задача о взвешенной вершинной раскраске графов. Применительно к этой задаче, будет сделан обзор некоторых известных способов редукции графов, а также сформулированы новые результаты такого типа. В качестве приложения эти методы будут использованы для уменьшения количества случаев с открытым сложностным статусом рассматриваемой задачи для наследственных классов графов с двумя связными пятивершинными запретами