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

摘要

This paper presents an O(n(m + n log n)log n) time algorithm to solve the minimum cost tension problem, where n and m denote the number of nodes and number of arcs, respectively. The algorithm is inspired by Orlin (Oper Res 41:338-350, 1993) and improves upon the previous best strongly polynomial time of O(max{m(3)n, m(2) log n(m + n log n)}) due to Ghiyasvand (J Comb Optim 34:203-217, 2017).