Теоретический семинар (весна 2018)

Название: Алгоритмы и нижние оценки для задачи Target Set Selection

Время: 17 мая, 18:30

Место: Академический университет, аудитория 431

Докладчик: Данил Сагунов

 

Мы рассмотрим задачу Target Set Selection. Входом задачи является неориентированный граф,

в котором каждой вершине сопоставлено некоторое неотрицательное число - пороговое значение,

и числа k, l. Требуется ответить на вопрос, можно ли заразить вершин графа изначально так,

Название: Задача 3-раскраски при ограничениях на минимальную степень графа

Время: 26 апреля, 16:30

Место: АУ, аудитория 431

Докладчик: Воронова Надя

Описание:

В прошлый раз мы рассмотрели сложность задачи 3-раскраски при ограничениях снизу на минимальную степень графа, показали, что задача остаётся сложной при mindeg > n^(1-c) для c < 1. 

В этот мы:

Название: Задача 3-раскраски при ограничениях на минимальную степень графа
Время: 19 апреля, 18:30
Место: АУ, аудитория 431
Докладчик: Воронова Надежда
 
Описание:
 
Рассмотрим, как ведёт себя задача 3-раскраски при ограничениях снизу на минимальную степень графа.
- Покажем алгоритм для 3-раскраски, время работы которого зависит от mindeg(G), и который при mindeg(G) > 14 работает быстрее наилучшего алгоритма для общего случая
- Докажем, что задача всё ещё остаётся сложной при подобных ограничениях

Доклад по статье «A Complete Public-Key Cryptosystem»  Д. Григорьева, Э. А. Гирша и К. Первышева

Время: 16:30, 12 апреля.
Место: АУ, 431.

Алгоритм для Target Set Selection с константными ограничениями на пороговые значения

Время: 22 февраля, 18:30

Место: СПбАУ РАН

Докладчик: Данил Сагунов

 

Описание:

 

Мы закончим рассматривать экспоненциальный алгоритм для Minimum Perfect Target Set

и покажем, как этот алгоритм изменяется в случае решения задачи Target Set Selection.

 

 

Материалы доклада 15 февраля. 

Название: Алгоритм для Target Set Selection с константными ограничениями на пороговые значения

Время: 15 февраля, 16:30

Место: ПОМИ РАН, ауд. 402

Докладчик: Данил Сагунов

 

Описание:

 

Мы рассмотрим NP-трудную задачу Target Set Selection, представляющую собой модель распространения мнения в социальных сетях.

Будет предложен точный алгоритм, позволяющий решать задачу быстрее 2^n, если пороговые значения распространения ограничены

некоторой фиксированной константой.

В докладе будет доказана экспоненциальная нижняя оценка на размер свободных бинарных диаграмм решений (FBDD) для выполнимых цейтинских формул на графе-экспандере. 

В данном докладе будут объяснены понятия цейтинских формул, свободных бинарных диаграмм решений (FBDD) и упорядоченных бинарных диаграмм решений (OBDD).