Min-cost-flow preserving bijection between subgraphs and orientations

Izhak Elmaleh, Ohad N. Feldheim

Consider an undirected graph $G=(V,E)$. A subgraph of $G$ is a subset of its edges, whilst an orientation of $G$ is an assignment of a direction to each edge. Provided with an inte…