Identifying a minimum cut and/or a maximum flow using balancing of vertex excesses

摘要

A representation of a network having vertices connected by arcs is provided, where the network exhibits a pseudoflow. Arcs on which moves are to be performed are iteratively chosen for balancing excesses of vertices across the arcs until a stopping rule is satisfied. After the stopping rule is satisfied, further processing is performed to identify at least one of a minimum cut and/or maximum flow.