-
85浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0评论
-
引用
期刊论文
A polynomial solvable minimum risk spanning tree problem with interval data
European Journal of Operational Research,2009,198(1):43-46 | 2009年10月01日 | https://doi.org/10.1016/j.ejor.2008.06.039
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 , each link 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.
学者未上传该成果的PDF文件,请等待学者更新
本学者其他成果
同领域成果