Заседание научного семинара лаборатории ЛАТАС

Очередное заседание научного семинара лаборатории ЛАТАС 19 января в 16:00 (среда)

Заседание семинара будет проходить очно в лаборатории ЛАТАС к.401 (ул. Родионова 136).

Тема: Задачи разбиения графов на связные полные двудольные графы и простые цепи одинаковой длины: прикладные и сложностные аспекты

Докладчик: Олег Дугинов (БГУ, Минск)

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