TY - JOUR

T1 - Bottleneck flows in unit capacity networks

AU - Punnen, Abraham P.

AU - Zhang, Ruonan

N1 - Funding Information:
✩ This work was supported by an NSERC discovery grant awarded to Abraham P. Punnen. * Corresponding author. E-mail addresses: apunnen@sfu.ca (A.P. Punnen), rza1@sfu.ca (R. Zhang).

PY - 2009/2/28

Y1 - 2009/2/28

N2 - 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 {m3 / 2, n2 / 3 m} log n) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O (min {m3 / 2, n2 / 3 m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in O (min {m (n log n)2 / 3, m3 / 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.

AB - 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 {m3 / 2, n2 / 3 m} log n) time by showing that the maximum flow problem on an almost unit capacity graph can be solved in O (min {m3 / 2, n2 / 3 m}) time. We then propose a faster algorithm to solve the unit capacity BNFP in O (min {m (n log n)2 / 3, m3 / 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.

KW - Algorithms

KW - Combinatorial problems

KW - Graphs

KW - Minimum cost flow

KW - Network flows

KW - Unit capacity

UR - http://www.scopus.com/inward/record.url?scp=58849155917&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2008.11.011

DO - 10.1016/j.ipl.2008.11.011

M3 - Article

AN - SCOPUS:58849155917

SN - 0020-0190

VL - 109

SP - 334

EP - 338

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -