A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
From MaRDI portal
Publication:750277
DOI10.1007/BF01580869zbMath0713.90028OpenAlexW2029479369MaRDI QIDQ750277
Publication date: 1990
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01580869
Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems ⋮ Equivalence of the primal and dual simplex algorithms for the maximum flow problem ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ On strongly polynomial dual simplex algorithms for the maximum flow problem ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Strongly polynomial dual simplex methods for the maximum flow problem ⋮ An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ 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 ⋮ Maximum flow problem in wireless ad hoc networks with directional antennas ⋮ Exterior point simplex-type algorithms for linear and network optimization problems ⋮ Polynomial-time primal simplex algorithms for the minimum cost network flow problem ⋮ A new?old algorithm for minimum-cut and maximum-flow in closure graphs ⋮ On strongly polynomial variants of the MBU-simplex algorithm for a maximum flow problem with non-zero lower bounds ⋮ A polynomial-time simplex method for the maximum \(k\)-flow problem ⋮ Polynomial dual network simplex algorithms ⋮ A strongly polynomial simplex method for the linear fractional assignment problem ⋮ Computational investigations of maximum flow algorithms ⋮ On the maximum capacity augmentation algorithm for the maximum flow problem ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ The maximum flow problem: A max-preflow approach
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Use of dynamic trees in a network simplex algorithm for the maximum flow problem
- A data structure for dynamic trees
- A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
- Finding minimum-cost circulations by canceling negative cycles
- Improved Time Bounds for the Maximum Flow Problem
- A practicable steepest-edge simplex algorithm
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- A network simplex method
- A bad network problem for the simplex method and other minimum cost flow algorithms
This page was built for publication: A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time
