An Algorithm for Balanced Flows

The Balanced Network Search (BNS) is an algorithm which finds a maximum balanced flow in a balanced network \({N}\). This algorithm is a way of using network flows to solve a number of standard problems, including maximum matchings, the factor problem, maximum capacitated \(b\)-matchings, etc., in general graphs. The value of a maximum balanced flow equals the capacity of a minimum balanced edge-cut. Flow-carrying balanced networks contain structures called generalized blossoms. They are not based on odd cycles. Rather they are the connected components of a residual sub-network of \({N}\). An algorithm is given for finding a maximum balanced flow, by constructing complementary pairs of valid augmenting paths.