一个新的最大流问题增载轨算法  

New Augmenting Path Algorithm for the Maximum Flow Problem

作　　者：张宪超[1] 江贺[1] 

机构地区：[1]大连理工大学软件学院,大连116024

出　　处：《小型微型计算机系统》2006年第9期1726-1730,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60503003)资助.

摘　　要：通过放松Ahujia和Orlin算法的约束，给出了一个新的增载轨算法．该算法实质上提供了一个构造、阻塞无环网络的策略，它可以在每次构造无环网络中得到更多的增载轨．从而进一步降低了找到每条增载轨的代价．实验表明，新的算法比Dinic算法快2～5倍，和目前实验性能最好的预流推进算法基本相近．说明增载轨类算法在实际性能方面未必落后于预流推进类算法．A new augmenting path algorithm is proposed in this paper by relaxing constraints of Ahujia ＆ Orlin. The new algorithm provides one new strategy to construct and block non-loop network to get more augmenting path. In this way, the cost of finding every augmenting path is further reduced. Experiments had shown that the new algorithm is 2-5 times faster than Dinic＇s algorithm, nearly the same as the best implementation of the Pre-flow Push algorithm, showing that augmenting path algorithm is not necessarily worse than Pre-flow Push algorithm in term of practical performance.

关 键 词：最大流 增载轨算法 预流推进算法 实验性能 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]