NEW MAXIMUM FLOW ALGORITHMS BY MA ORDERMGS AND SCALING
Satoru Fujishige, Shigueo Isotani · Journal of the Operations Research Society of Japan · 2003
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 (mnlogt7) time, where TO 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.