This paper presents a strongly polynomial time algorithm for the minimum cost tension problem, which runs in O(max { m3n, m2log n(m+ nlog n) }) time, where n and m denote the number of nodes and number of arcs, respectively. Our algorithm improves upon the previous strongly polynomial time of O(n4m3log n) due to Hadjiat and Maurras (Discret Math 165(166):377–394, 1997). © 2016, Springer Science+Business Media New York.
