A maximum flow algorithm using maximum adjacency ordering

Maximum adjacency (MA) ordering has effectively been applied to graph connectivity problems by Nagamochi and Ibaraki. In this note we show an application of MA ordering to the maximum flow problem with integral capacities to get a new polynomial-time algorithm. A scaling version of our algorithm runs in O(mn log U) time, where m is the number of arcs, n the number of vertices, and U the maximum capacity.