Faster scaling algorithms for network problems

Harold N. Gabow, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

299 Scopus citations


This paper presents algorithms for the assignment problem, the transportation problem, and the minimum-cost flow problem of operations research. The algorithms find a minimum-cost solution, yet run in time close to the best-known bounds for the corresponding problems without costs. For example, the assignment problem (equivalently, minimum-cost matching in a bipartite graph) can be solved in O(√nm log(nN)) time, where n, m, and N denote the number of vertices, number of edges, and largest magnitude of a cost; costs are assumed to be integral. The algorithms work by scaling. In each scaled problem an approximate optimum solution is found, rather than an exact optimum.

Original languageEnglish (US)
Pages (from-to)1013-1036
Number of pages24
JournalSIAM Journal on Computing
Issue number5
StatePublished - 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Faster scaling algorithms for network problems'. Together they form a unique fingerprint.

Cite this