On the equivalence of constrained and unconstrained flows

AbstractA linear-time algorithm that reduces the set of flows on a directed graph with an additional linear equality constraint to that of lower dimensional subgraphs is presented. These subgraphs form a partition of the original graph, and at most one is singly constrained while the others are unconstrained. If none of the subgraphs is constrained, the algorithm provides a linear-time recognition and transformation of constrained to unconstrained network flows. Applications to constrained network flow optimization are given