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

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

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

Тема: L = SL.

Abstract

Доклад посвящён недавно появившейся статье Omer Reingold ``Undirected ST-Connectivity in Log-Space'', в которой был предложен детерминированный и использующий только

памяти алгоритм, решающий задачу о наличии пути между двумя данными вершинами в неориентированном графе. Напомним, что в классический метод Савича требует

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

при более чем полиномиальном времени, доказывает равенство классов L и SL. А также позволяет строить, используя только логарифмический объем памяти, универсальную последовательность обхода для регулярных графов (при незначительном ограничении на разметку рёбер) --- последовательность номеров рёбер, следуя которой, можно выбраться из любого лабиринта.