带区间数据的最小风险斯坦纳树问题  

THE MINIMUM STEINER TREE PROBLEMS WITH INTERVAL DATA

作　　者：陈旭瑾[1] 胡捷[1] 胡晓东[1] 

机构地区：[1]中国科学院数学与系统科学研究院应用数学所,北京100190

出　　处：《系统科学与数学》2008年第11期1310-1322,共13页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(70221001;10531070;10771209.10721101);中国科学院知识创新工程重要方向(kjcxyw-s7)项目资助.

摘　　要：考虑了在带区间数据的不确定网络中,最小风险和模型以及最小最大风险模型下的斯坦纳树问题.它们推广了相应模型下的最短路问题和最小支撑树问题,在网络设计中具有更加广泛的应用.我们分别给出了这两个模型下斯坦纳树问题的近似算法,并对算法性能儆了理论分析和证明.结果显示我们的算法具有优良的常数逼近的性质,能在多项式时间内算出令人满意的解.Based on the models of minimum risk sum and minimum maximum risk, this paper is concerned with the minimum Steiner tree problems in uncertain networks with interval data. Generalizing the shortest path problem and the minimum spanning tree problem in the cresponding risk models, these minimum risk Steiner tree problems have wider real-world applications in network design. The approximation algorithms of the Steiner tree problems in these two models is presented. Finally, the constant approximation ratios of the algorithms are theoretically analyzed and proved.

关 键 词：斯坦纳树问题 区间数据 不确定网络 近似算法 

分 类 号：O157.5[理学—数学]