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

DOI10.1007/BF01580604zbMATH Open0795.90022OpenAlexW2069324954MaRDI QIDQ688924FDOQ688924

Authors: Donald K. Wagner, Hong Wan 

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

Recommendations

• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• Strongly polynomial dual simplex methods for the maximum flow problem
• On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem
• On strongly polynomial dual simplex algorithms for the maximum flow problem
• A polynomial dual simplex algorithm fot the generalized circulation problem.

zbMATH Keywords

polynomial timecirculation problemnetwork simplex method

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• A faster polynomial algorithm for the constrained maximum flow problem
• A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
• Approximation Algorithms for k-Hurdle Problems
• Title not available (Why is that?)
• A polynomial dual simplex algorithm fot the generalized circulation problem.
• Approximation algorithms for \(k\)-hurdle problems
• A primal simplex variant for the maximum-flow problem
• On the \(k\)-cut subgraph polytope
• A note on the problem of \(r\) disjoint \((s, t)\)-cuts and some related issues

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688924)