带时间和成本约束的随机流网络可靠度的计算

给出了一种求满足传输量要求的时间和成本约束下网络的所有极小状态(下界点集)的简单方法.讨论了基于下界点集合的可靠度的容斥原理公式,直接应用容斥原理公式会有很多相互抵消的项.如果所有的数据通过k条不相交的极小路径同时传输,只需讨论r-1项和r(1<r≤k)项组合相消情况(假设k小于下界点数),其他组合项的相消情况也能确定.最后给出了确定相消项的算法.利用所给算法使可靠度的计算公式得到大大简化.