网络最大流问题算法研究

摘要

该文得到了一个突破流分解障碍的整数容量最大流问题的混合算法,这是第二个突破流分解障碍的通用算法,它的时间复杂度比第一个突破分解障碍算法的时间复杂度少了一个log(n<'2>/m)的因子;该文得到了小容量网络上的突破流分解障碍的算法.该文得到了一个新的增载轨算法,大量的实验测试表明它比目前实验性能最好的增载轨算法(Dinic算法)快2-5倍.该文得到了一个O(n)时间的单位容量平面网络的最大流算法.b