Семинары

Рассылка: https://groups.google.com/forum/#!forum/spb-algo



Решение задачи о k-пути в неориентированных графах за 2^{3k/4}

Докладчик: 
Александр Куликов
Дата: 
Monday, October 6, 2014 - 18:00
Место: 
Аудитория 106, ПОМИ
Аннотация: 

Будет рассказан недавний алгоритм Бьорклунда, Хусфельда, Каски, Коивисто решения задачи нахождения просто пути длины k в неориентированном графе за время O^*(2^{3k/4}). Из этого, в частности, следует, что найти гамильтонов путь в неориентированном графе можно быстрее 2^n. Алгоритм основан на построении специального многочлена, в котором каждому простому k-пути соответствует уникальный моном, а самопересекающиеся k-пути разбиваются на пары с одинаковыми мономами. Таким образом, данный многочлен тождественно равен нулю в поле характеристики два (достаточно большого размера) тогда и только тогда, когда в графе есть простой k-путь.



Схемы со средней входящей степенью

Докладчик: 
Дмитрий Соколов
Дата: 
Monday, September 29, 2014 - 18:00
Место: 
ПОМИ, аудитория 106
Аннотация: 

В докладе мы рассмотрим булевы схемы, в которых входная степень гейта ограничена линейной функцией от числа переменных. Мы докажем оценку \Omega(log^2 n) на явную функцию для подобных схем. Будет продемонстрирован метод применения коммуникационной сложности для доказательства нижних оценок на размер схем.



Introduction to online algorithms

Докладчик: 
Sushmita Gupta
Дата: 
Monday, September 22, 2014 - 18:00
Место: 
ПОМИ РАН, Мраморный зал
Аннотация: 

In this lecture we will survey the area of online algorithms using some well known examples and problems. We will look at classical approaches as well as new ones, and discuss the underlying principles and objectives that drive research in the online paradigm.



Задача редактирования графа до графа с заданными степенями

Докладчик: 
Пётр Головач
Дата: 
Thursday, September 18, 2014 - 18:00
Место: 
ПОМИ РАН, Мраморный зал
Аннотация: 

The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks for a graph $G$, non-negative integers $d,k$ and a function $\delta \colon V(G) \to \{1,...,d\}$, whether it is possible to obtain a connected graph $G’$ from $G$ such that the degree of $v$ is $\delta(v)$ for any vertex $v$ by at most $k$ edge editing operations. As the problem is NP-complete even if $\delta(v)=2$, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by $d+k$. For the special case $\delta(v)=d$, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. We also investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. In particular, we obtain polynomial-time algorithms for the Edge Editing to an Eulerian Graph problem and its directed variant.



2 11/23 - приближение для задачи о кратчайшей надстроке

Докладчик: 
Евгений Служаев
Дата: 
Monday, September 15, 2014 - 18:30
Место: 
Аудитория 203
Аннотация: 

Будет рассказано об алгоритме Марчина Мухи и получено 2 11/23 - приближение для задачи о кратчайшей надстроке, которое является наилучшим из известных на сегодняшний день приближений для этой задачи.


Pages