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) root log n}) time, an improvement by a factor of at least 3 root log n. For dense graphs, the improvement is by a factor of root log n. On unit capacity simple graphs, we show that BNFP can be solved in O root n log n) time, an improvement by a factor of root log n. As a consequence we have an O(m root n log n) algorithm for the BTP with unit arc capacities. (C) 2008 Elsevier B.V. All rights reserved.