Home

Семинар 17 декабря 2004 года

Пятница, 17 декабря, комната 106. Начало в 17:30.

Докладчик: К. Первышев.

Тема: L = SL.

Abstract

Доклад посвящён недавно появившейся статье Omer Reingold ``Undirected ST-Connectivity in Log-Space'', в которой был предложен детерминированный и использующий только $ O(log N) $ памяти алгоритм, решающий задачу о наличии пути между двумя данными вершинами в неориентированном графе. Напомним, что в классический метод Савича требует $ O((log N)^2) $ памяти, работая, правда, и для ориентированных графов. В основе нового метода лежит эффективное повышение связности исходного графа (превращение его в экспандер) при сохранении регулярности. Данный алгоритм значительно улучшает предыдущие достижения --- память $ O((log N)^{4/3}) $ при более чем полиномиальном времени, доказывает равенство классов L и SL. А также позволяет строить, используя только логарифмический объем памяти, универсальную последовательность обхода для регулярных графов (при незначительном ограничении на разметку рёбер) --- последовательность номеров рёбер, следуя которой, можно выбраться из любого лабиринта.