### Abstract

We give a fast algorithm for computing a minimum-cost maximum flow in a series-parallel network. On an m-edge network, the algorithm runs in O(m log m) time. The space needed is O(m) if only the cost of the minimum-cost flow is desired, or O(m log m) if the entire flow is needed. This space bound can be reduced to O(m log^{*} m) without increasing the running time. The idea behind the algorithm is to represent a set of augmenting paths by a balanced search tree.

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

Pages (from-to) | 416-446 |

Number of pages | 31 |

Journal | Journal of Algorithms |

Volume | 15 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1993 |

### All Science Journal Classification (ASJC) codes

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

## Fingerprint Dive into the research topics of 'Finding the minimum-cost maximum flow in a series-parallel network'. Together they form a unique fingerprint.

## Cite this

Booth, H., & Tarjan, R. E. (1993). Finding the minimum-cost maximum flow in a series-parallel network.

*Journal of Algorithms*,*15*(3), 416-446. https://doi.org/10.1006/jagm.1993.1048