An $$O(n(m+n\log n)\log n)$$ time algorithm to solve the minimum cost tension problem

Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice-Hall, Englewood Cliffs Ahuja RK, Hochbaum DS, Orlin JB (2003) Solving the convex cost integer dual network flow problem. Manage Sci 49:950–964 Bachelet B, Duhamel C (2009) Aggregation approach for the minimum binary cost tension problem. Eur J Oper Res 197:837–841 Bachelet B, Mahey P (2003) Minimum convex-cost tension problems on series-parallel graphs. RAIRO Oper Res 37(4):221–234 Bachelet B, Mahey P (2004) Minimum convex piecewise linear cost tension problem on quasi-k series-parallel graphs. 4OR Q J Eur Oper Res Soc 2(4):275–291 Berge C, Ghouila-Houri A (1962) Programming, games and transportation networks. Wiley, New York Edmonds I, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. J Assoc Comput Mach 19:248–264 Fredman ML, Tarjan RE (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J Assoc Comput Mach 34:596–615 Gabow HN (1985) Scaling algorithms for network problems. J Comput Syst Sci 31:148–168 Ghiyasvand M (2012) An \(O(m(m+n\log n)\log (nC))\)-time algorithm to solve the minimum cost tension problem. Theor Comput Sci 448:47–55 Ghiyasvand M (2012) A polynomial-time implementation of Pla’s method to solve the MCT problem. Adv Comput Math Its Appl 1(2):104–109 Ghiyasvand M (2014) Scaling implementation of a tension rectification algorithm to solve the feasible differential problem. Sci Iran 21:980–987 Ghiyasvand M (2017) A faster strongly polynomial time algorithm to solve the minimum cost tension problem. J Comb Optim 34:203–217 Ghouila-Houri A (1964) Flots et tension dans un graphe, Ph.D Thesis, Gauthier-Villars, Paris Goldberg AV, Tarjan RE (1990) Finding minimum-cost circulations by successive approximation. Math Oper Res 16:430–466 Guler C (2008) Inverse tension problems and monotropic optimization. WIMA Report Hadjiat M (1998) Penelope’s graph: a hard minimum cost tension instance. Theor Comput Sci 194:207–218 Hadjiat M, Maurras JF (1997) A strongly polynomial algorithm for the minimum cost tension problem. Discrete Math 165(166):377–394 Hamacher HW (1985) Min cost tension. J Inf Optim Sci 6(3):285–304 Karzanov A, McCormick ST (1997) Polynomial methods for separable convex optimization in unimodular linear spaces with applications. SIAM J Comput 26:1245–1275 Maurras JF (1994) The maximum cost tension problem. In: Proceedings Conference, European chapter on combinatorial optimization (ECCO VII), Italy Orlin JB (1993) A faster strongly polynomial minimum cost flow algorithm. Oper Res 41:338–350 Pla JM (1971) An out-of-kilter algorithm for solving minimum cost potential problems. Math Program 1:275–290 Rockafeller RT (1984) Network flows and monotropic optimization. Wiley, New York