您当前所在位置: 首页 > 学者

陈旭瑾

  • 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

URL:https://www.sciencedirect.com/science/article/abs/pii/S0377221708005018

摘要/描述

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文件,请等待学者更新

我要评论

全部评论 0

本学者其他成果

    同领域成果