A simple version of Karzanov's blocking flow algorithm

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n - 1 so-called 'blocking flow' problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n2). Karzanov devised the first O(n2)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n2)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.

Original languageEnglish (US)
Pages (from-to)265-268
Number of pages4
JournalOperations Research Letters
Volume2
Issue number6
DOIs
StatePublished - Mar 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Maximum flow problem
  • graph algorithm

Fingerprint

Dive into the research topics of 'A simple version of Karzanov's blocking flow algorithm'. Together they form a unique fingerprint.

Cite this