一种不确定图中最可靠最大流问题的解决方案

吕建华1张柏礼1生衍1田伟2

1.东南大学; 2.南京弘毅电气自动化有限公司;

摘要：

最可靠最大流是不确定图中可靠性最高的最大流,它是传统最大流问题在不确定图上的自然延伸.现有的最可靠最大流算法SDBA时间复杂性较高,无法满足实际中不同应用的需求,为此,文中提出一种具有普遍适用性的最可靠最大流解决方案.该方案包含面向不同需求的3种算法:基于负权群落消去的NWCE算法、基于时间约束优先单环消去的SPEA-t算法和基于概率阈值约束优先单环消去的SPEA-p算法.其中.NWCE算法借鉴最小费用最大流的“流平移”思想并基于文中提出的负权群落概念,在辅助剩余图中不断地消去可使可靠性增加而流量不变的负权群落,可证当消去所有负权群落时对应的最大流即为最可靠最大流.根据负权群落中由单环组成的群落占很高…展开v

关键词：不确定图、最大流、流可靠性

所属期刊栏目：37

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61073059,61232007,61300200

在线出版日期：2014-11-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：2084-2095