City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Поиск всех кратчайших путей в графе и min-plus умножение матриц
Communication Complexity

What: Lecture
When: Sunday, 14 February 2016, 11:15–12:50
Where: ПОМИ РАН

Description

Задача поиска всех кратчайших расстояний в графе. Алгоритм для невзвешенного графа со временем работы \(n^\omega\). Связь с min-plus умножение матриц.

Video