A primal simplex variant for the maximum-flow problem

DOI10.1002/NAV.3800310107MaRDI QIDQ3316928zbMATH OpenOpenAlexFDO

Authors Fred Glover, John Mote, David Whitman, Darwin D. Klingman

Publication date 1984

Published in Naval Research Logistics Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/nav.3800310107

zbMATH Keywords

comparison of algorithmscomputational evaluationlabel treemaximum flow problemsnetwork flownumerical studyprimal simplexupdate techniques

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Equivalence of the primal and dual simplex algorithms 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
• scientific article; zbMATH DE number 4174642
• A polynomial-time simplex method for the maximum \(k\)-flow problem
• A new approach to the maximum-flow problem
• scientific article; zbMATH DE number 1187162
• A specialized network simplex algorithm for the constrained maximum flow problem
• scientific article; zbMATH DE number 795215
• Polynomial-time primal simplex algorithms for the minimum cost network flow problem
• A NETWORK SIMPLEX METHOD FOR THE MAXIMUM BALANCED FLOW PROBLEM

Cites work

• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• scientific article; zbMATH DE number 3121292 (Why is no real title available?)
• scientific article; zbMATH DE number 3791939 (Why is no real title available?)
• Maximal Flow Through a Network
• Pivot Strategies for Primal-Simplex Network Codes
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(9)

• Computational investigations of maximum flow algorithms
• Equivalence of the primal and dual simplex algorithms for the maximum flow problem
• A cutting plane algorithm for minimum perfect 2-matchings
• A note on specialized versus unspecialized methods for maximum-flow problems
• Solving matching problems with linear programming
• scientific article; zbMATH DE number 45131 (Why is no real title available?)
• Implementing Goldberg's max-flow-algorithm ? A computational investigation
• A specialized network simplex algorithm for the constrained maximum flow problem
• Solution of large-scale symmetric travelling salesman problems

This page was built for publication: A primal simplex variant for the maximum-flow problem

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