An O(m(m+nlogn)log(nC))-time algorithm to solve the minimum cost tension problem

This paper presents a new polynomial-time algorithm to solve the minimum cost tension problem. It runs in O(m(m+nlogn)log(nC))-time, where n,m,C denote the number of nodes, number of arcs, and maximum arc capacity value of an arc cost, respectively. The algorithm improves the O(m2nlogC)-time algorithm of Maurras (1994) [20], . Also our algorithm, under the similarity assumption (Gabow, 1985) [12], , runs in O(m(m+nlogn)logn)-time, which improves the O(n4m3logn)-time algorithm of Hadjiat and Maurras (1997) [18].