## 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(n^{2}). Karzanov devised the first O(n^{2})-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n^{2})-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