Miu Cost Tensions

Abstract Tensions are functions p: E→ℝ defined on the aic set E of a directed graph satisfying p(C +)=p(C –) for all cycles C in G, where C + and C – are the sels of arcs having the opposite and the same direction as C, respectively. A min cost tension minimizes the linear cost . We develop tsvo algorithms for finding a min cost tension: the negative cut algorithm and the shortest augmenting cut algorithm. Both, negative and shortest augmenting cuts, can be found by means of lower capacitated network flows. An application to totally unimodular restricted linear programs is sketched.