Edge-cuts Optimized for Average Weight: a new alternative to Ford and Fulkerson

Scott Payne, Edgar Fuller, Cun-Quan Zhang

Let $G$ be a directed graph associated with a weight $w:E(G)\to R^{+}$. For an edge-cut $Q$ of $G$, the average weight of $Q$ is denoted and defined as $w_{ave}(Q)=\frac{\s…