PRACTICAL EFFICIENCY OF MAXIMUM FLOW ALGORITHMS USING MA ORDERINGS AND PREFLOWS
Yuji Matsuoka, Satoru Fujishige · Journal of the Operations Research Society of Japan · 2005
Fujishige proposed a polynomial-time maximum flow algorithm using maximum adjacency (MA) orderings. Computational results by Fujishige and Isotani showed that the algorithm was slower in practice than Goldberg and Tarjan's algorithm. In this paper we propose an improved version of Fujishige's algorithm using preflows. Our computational results show that the improved version is much faster than the original one in practice.