On efficient algorithms for bottleneck path problems with many sources

Optimization Letters. 2024. Vol. 18. P. 1273–1283.

Kirill V. Kaymakov, Dmitry S. Malyshev

For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or max min ) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise as subproblems
in the known maximum flow problem, having applications in many reallife tasks. For any graph with n vertices and m edges, they can be solved in O(m) and O(t(m, n)) times, respectively, where t(m, n) = min(m + n log(n),m(m, n)) and
(⋅, ⋅) is the inverse Ackermann function. In this paper, we generalize of the bottleneck path problems by considering their versions with k sources. For the first of them, where k pairs of sources and targets are (offline or online) given, we present an O((m + k) log(n))-time randomized and an O(m + (n + k) log(n))-time deterministic algorithms for the offline and online versions, respectively. For the second one, where the bottleneck values are found between k sources and all targets, we present an O(t(m, n) + kn)-time offline/online algorithm.

Keywords: Computational Complexity, design and analysis of algorithms, Bottleneck path problem

Publication based on the results of: Network models, optimization and computational complexity (2024)