Семинар лаборатории теоретической информатики: "Исследование количества максимальных и наибольших независимых множеств в некоторых классах деревьев". Докладчик: Д. Талецкий (НИУ ВШЭ, Нижний Новгород)

20 марта на семинаре лаборатории теоретической информатики
состоится доклад Дмитрия Талецкого (НИУ ВШЭ, Нижний Новгород)
"Исследование количества максимальных и наибольших независимых множеств 
в некоторых классах деревьев"

Аннотация.
Первая часть доклада посвящена задаче максимизации количества наибольших независимых множеств. Для любого n в классе деревьев со степенями всех вершин не более чем d, где d >= 3, были полностью описаны все n-вершинные деревья, имеющие максимальное количество наибольших независимых множеств среди всех таких деревьев. При этом в случае четного n экстремальное дерево всегда единственно, а в случае нечетного n единственность может и не иметь места. Аналогичный результат получен и для класса n-вершинных деревьев, имеющих ровно l листьев, где 3 <= l <= n-1. В этом случае экстремальное дерево единственно при любых значениях параметров n и l.

Во второй части доклада рассматриваются две задачи о перечислении 
максимальных независимых множеств. Для любого n > 3 полностью описаны 
n-вершинные деревья, не содержащие листьев-дубликатов, имеющие 
наименьшее количество максимальных независимых множеств среди всех таких деревьев. Кроме того, для полных q-арных деревьев получена асимптотика количества максимальных независимых множеств при высоте деревьев, стремящейся к бесконечности для случая q=2 и для случая всех достаточно больших значений q.

Семинар пройдет с 18:10 до 19:30 в аудитории 503 ФКН.
Заказ пропуска: Чернышова Дина dchernyshova@hse.ru