  In this paper the robust recoverable spanning tree problem with interval edge
costs is considered. The complexity of this problem has remained open to date.
It is shown that the problem is polynomially solvable, by using an iterative
relaxation method. A generalization of this idea to the robust recoverable
matroid basis problem is also presented. Polynomial algorithms for both robust
recoverable problems are proposed.
