Bottleneck flows in unit capacity networks

Abraham P. Punnen*, Ruonan Zhang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)334-338
Number of pages5
JournalInformation Processing Letters
Issue number6
Publication statusPublished - 28 Feb 2009
Externally publishedYes


  • Algorithms
  • Combinatorial problems
  • Graphs
  • Minimum cost flow
  • Network flows
  • Unit capacity


Dive into the research topics of 'Bottleneck flows in unit capacity networks'. Together they form a unique fingerprint.

Cite this