Bottleneck flows in unit capacity networks

The bottleneck network flow problem (BNFP) is a generalization of several well-studied bottleneck problems such as the bottleneck transportation problem (BTP), bottleneck assignment problem (BAP), bottleneck path problem (BPP), and so on. The BNFP can easily be solved as a sequence of O (log n) maximum flow problems on almost unit capacity networks. We observe that this algorithm runs in O (min {m^{3 / 2}, n^{2 / 3} m} log n) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O (min {m^{3 / 2}, n^{2 / 3} m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in O (min {m (n log n)^{2 / 3}, m^{3 / 2} sqrt(log n)}) time, an improvement by a factor of at least root(log n, 3). For dense graphs, the improvement is by a factor of sqrt(log n). On unit capacity simple graphs, we show that BNFP can be solved in O (m sqrt(n log n)) time, an improvement by a factor of sqrt(log n). As a consequence we have an O (m sqrt(n log n)) algorithm for the BTP with unit arc capacities.