## Abstract

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n^{2} log^{2}n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^{ε}) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).

Original language | English (US) |
---|---|

Pages (from-to) | 447-474 |

Number of pages | 28 |

Journal | Journal of Algorithms |

Volume | 17 |

Issue number | 3 |

DOIs | |

State | Published - Nov 1994 |

## All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics