Заседание научного семинара лаборатории ЛАТАС
Speaker: Kirill Kaymakov (Higher School of Economics)
Title: Bottleneck path problems with many sources and efficient algorithms for their solving
In this report the speaker will tell about generalization of the bottleneck path problems by considering their versions with k sources. For the Multi-Pair Bottleneck Path Problem, where k pairs of sources and targets are (offline or online) given, the O((m + k) log(n))- and O(m + (n + k) log(n))-time algorithms for the offline and online its versions will be introduced. For the Multi-Source Bottleneck Paths Problem, where the bottleneck values are found between k sources and all targets, an O(t(m, n) + kn)-time offline/online algorithm will be presented.
Приглашаются все желающие.
Явка аспирантов школы компьютерных наук обязательна.