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)G=(V,E), each link e∈Ee∈E can be established by paying a cost View the MathML sourcece∈[c̲e,c¯e], and accordingly takes a risk View the MathML sourcec¯e-cec¯e-c̲e 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.