A faster strongly polynomial time algorithm to solve the minimum cost tension problem |
| |
Authors: | Mehdi Ghiyasvand |
| |
Institution: | 1.Department of Mathematics, Faculty of Science,Bu-Ali Sina University,Hamedan,Iran |
| |
Abstract: | This paper presents a strongly polynomial time algorithm for the minimum cost tension problem, which runs in \(O(\max \{m^3n, m^2 \log n(m+n \log 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(n^4 m^3 \log n)\) due to Hadjiat and Maurras (Discret Math 165(166):377–394, 1997). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|