Finding a feasible flow in a strongly connected network

Bernhard Haeupler, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg-Rao maximum flow method by a constant factor.

Original languageEnglish (US)
Pages (from-to)397-398
Number of pages2
JournalOperations Research Letters
Volume36
Issue number4
DOIs
StatePublished - Jul 2008

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Keywords

  • Combinatorial algorithms
  • Feasible flow
  • Maximum flow
  • Network flow
  • Strongly connected network

Fingerprint Dive into the research topics of 'Finding a feasible flow in a strongly connected network'. Together they form a unique fingerprint.

Cite this