The MA-ordering max-flow algorithm is not strongly polynomial for directed networks

DOI10.1016/S0167-6377(03)00070-1zbMath1056.90016OpenAlexW2060011055MaRDI QIDQ1433655

Akiyoshi Shioura

Publication date: 1 July 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(03)00070-1

zbMATH Keywords

MA orderingMaximum flowStrongly polynomialWeakly polynomial

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10)

Related Items (1)

Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested

Cites Work

• A maximum flow algorithm using MA ordering.
• Theoretical Efficiency of the Algorithm “Capacity” for the Maximum Flow Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• NEW MAXIMUM FLOW ALGORITHMS BY MA ORDERMGS AND SCALING
• Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks

This page was built for publication: The MA-ordering max-flow algorithm is not strongly polynomial for directed networks