A polynomial-time simplex method for the maximum \(k\)-flow problem

DOI10.1007/BF01580604zbMath0795.90022OpenAlexW2069324954MaRDI QIDQ688924

Hong Wan, Donald K. Wagner

Publication date: 1 November 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580604

zbMATH Keywords

polynomial timenetwork simplex methodcirculation problem

Mathematics Subject Classification ID

Linear programming (90C05) Deterministic network models in operations research (90B10)

Related Items (4)

On the \(k\)-cut subgraph polytope ⋮ A note on the problem of \(r\) disjoint \((s, t)\)-cuts and some related issues ⋮ Approximation algorithms for \(k\)-hurdle problems ⋮ Approximation Algorithms for k-Hurdle Problems

Cites Work

• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• Edge-packings of graphs and network reliability
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• Maximal Flow Through a Network
• Disjoint (s, t)‐cuts in a network

This page was built for publication: A polynomial-time simplex method for the maximum \(k\)-flow problem