  This paper deals with the recoverable robust spanning tree problem under
interval uncertainty representations. A polynomial time, combinatorial
algorithm for the recoverable spanning tree problem is first constructed. This
problem generalizes the incremental spanning tree problem, previously discussed
in literature. The algorithm built is then applied to solve the recoverable
robust spanning tree problem, under the traditional interval uncertainty
representation, in polynomial time. Moreover, the algorithm allows to obtain,
under some mild assumptions about the uncertainty intervals,several
approximation results for the recoverable robust spanning tree problem under
the Bertsimas and Sim interval uncertainty representation and the interval
uncertainty representation with a budget constraint.
