A polynomial solvable minimum risk spanning tree problem with interval data

We propose and study a new model for the spanning tree problem with interval data, the Minimum Risk Spanning Tree (MRST) problem, that finds diverse applications in network design. Given an underlying network G=(V,E), each link e[set membership, variant]E can be established by paying a cost , and accordingly takes a risk of link failure. The MRST problem is to establish a spanning tree T in G of total cost not more than a given constant so that the risk sum over the links in T is minimized. We prove that the MRST problem can be solved in polynomial time, and thus has algorithmic aspect more satisfactory than the NP-hard robust spanning tree problem with interval data.