New maximum flow algorithms by maximum adjacency orderings and scaling

Maximum adjacency (MA) ordering has effectively been applied to graph connectivity problems by Nagamochi and Ibaraki. We show an application of MA ordering to the maximum flow problem to get a new polynomial-time algorithm and propose its scaling versions that run in O(mn log U) time, where m is the number of arcs, n the number of vertices, and U the maximum capacity. We give computational results, comparing our algorithms with those of Goldberg–Tarjan and Dinitz, to show behaviors of our proposed algorithms.