Пятница 21.04. Николай Мальковский (СПбГУ): "Распределенный алгоритм решения задачи о максимальном потоке"
PDMI seminars
Тема: Распределенный алгоритм решения задачи о максимальном потоке
Место: ауд. 203
Время: 21.04.2017, 17:15
Докладчик: Николай Мальковский (СПбГУ)
Abstract:
Задача о максимальном потоке и её двойственная -- задача о минимальном разрезе -- являются одними из наиболее изучаемых задач теории графов, на практике эти задачи часто встречаются в качестве промежуточных вычислений. В отдельных случаях возникает потребность решения задачи о максимальном потоке на вычислительной распределенной сети, где графом является топология взаимодействия этой сети. В таких ситуациях возникает вопрос: а можно ли решить задачу о максимальном потоке методом, не требующим синхронизации или сбора всей информации на одном из узлов сети? Алгоритмы, решающие какую-либо задачу в сети с такими ограничениями, обычно называются "распределенными". Как пример, задача синхронизации времени в сети допускает только распределенные методы решения. В докладе пойдет речь об одном распределенном алгоритме решения задачи о максимальном потоке и его связи с методами, основанными на электрических потоках и решении лапласиановых систем.