### Abstract

We introduce a gain-scaling technique for the generalized maximum flow problem. Using this technique, we present three simple and intuitive polynomial-time combinatorial algorithms for the problem. Truemper's augmenting path algorithm is one of the simplest combinatorial algorithms for the problem, but runs in exponential-time. Our first algorithm is a polynomial-time variant of Truemper's algorithm. Our second algorithm is an adaption of Goldberg and Tarjan's preflowpush algorithm. It is the first polynomial-time preflow-push algorithm in generalized networks. Our third algorithm is a variant of the Fat-Path capacity-scaling algorithm. It is much simpler than Radzik's variant and matches the best known complexity for the problem.We discuss practical improvements in implementation.

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

Title of host publication | Integer Programming and Combinatorial Optimization - 6th International IPCO Conference, 1998, Proceedings |

Editors | E. Andrew Boyd, Robert E. Bixby, Roger Z. Rios-Mercado |

Publisher | Springer Verlag |

Pages | 310-324 |

Number of pages | 15 |

ISBN (Print) | 354064590X, 9783540645900 |

DOIs | |

State | Published - Jan 1 1998 |

Externally published | Yes |

Event | 6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998 - Houston, United States Duration: Jun 22 1998 → Jun 24 1998 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1412 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998 |
---|---|

Country | United States |

City | Houston |

Period | 6/22/98 → 6/24/98 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Simple generalized maximum flow algorithms'. Together they form a unique fingerprint.

## Cite this

*Integer Programming and Combinatorial Optimization - 6th International IPCO Conference, 1998, Proceedings*(pp. 310-324). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1412). Springer Verlag. https://doi.org/10.1007/3-540-69346-7_24