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 is an element of E can be established by paying a Cost c(e) is an element of [(c) under bar (e), (c) over bar (e)], and accordingly takes a risk (c) over bar (e)-c(e)/(c) over bar (e)-(c) under bar (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. (C) 2008 Elsevier B.V. All rights reserved.