Поиск всех кратчайших путей в графе и min-plus умножение матриц
Эффективные алгоритмы и коммуникационная сложность


Что: Лекция
Когда: Воскресенье, 14 февраля 2016, 11:15–12:50
Где: ПОМИ РАН

Описание

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

Видео