A faster strongly polynomial time algorithm to solve the minimum cost tension problem

作者：Ghiyasvand Mehdi^*

来源：Journal of Combinatorial Optimization, 2017, 34(1): 203-217.

DOI：10.1007/s10878-016-0070-4

• Tension problems
• The minimum cost tension problem
• Strongly polynomial time

This paper presents a strongly polynomial time algorithm for the minimum cost tension problem, which runs in 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 due to Hadjiat and Maurras (Discret Math 165(166):377-394, 1997).

• 出版日期2017-7