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 language | English (US) |
---|---|
Pages (from-to) | 265-268 |
Number of pages | 4 |
Journal | Operations Research Letters |
Volume | 2 |
Issue number | 6 |
DOIs | |
State | Published - Mar 1984 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Applied Mathematics
- Industrial and Manufacturing Engineering
- Management Science and Operations Research
Keywords
- Maximum flow problem
- graph algorithm