Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482503 | European Journal of Operational Research | 2009 | 4 Pages |
Abstract
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 ce∈[c̲e,c¯e], and accordingly takes a risk c¯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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Xujin Chen, Jie Hu, Xiaodong Hu,