Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem

DOI10.1287/moor.16.2.272zbMath0743.90108OpenAlexW2091720300MaRDI QIDQ3978616

Robert Endre Tarjan

Publication date: 25 June 1992

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/efc3ab15de84c7e619f8dbc8bff2fb284b41a737

zbMATH Keywords

minimum cost circulationsimplex type algorithm\(n\)-vertex networkpivot selection rule

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (8)

Random walks, totally unimodular matrices, and a randomised dual simplex algorithm ⋮ A polynomial time primal network simplex algorithm for minimum cost flows ⋮ A new pivot selection rule for the network simplex algorithm ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ Use of dynamic trees in a network simplex algorithm for the maximum flow problem ⋮ Polynomial-time primal simplex algorithms for the minimum cost network flow problem ⋮ Polynomial dual network simplex algorithms

This page was built for publication: Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem