网络最优化中的一个扩容算法

指出了网络最小割集与网络瓶颈的关系,提出了解决网络瓶颈问题的一个优化扩容算法,并分析了算法复杂性.算法通过在给出了容量的网络中全局正向分段引入虚拟发点、构造扩容网络搜索全部最小割集;对于指定的网络最大流量,算法反向逐级计算各个最小割集弧组相应的调整量,通过增加调整量来重新布局各弧的容量,逐级回代直至恢复原网络拓扑结构,从而改善网络的通行能力,解决网络瓶颈问题.