Release Time:2019-03-10  Hits:

Indexed by: Journal Article

Date of Publication: 2006-09-30

Journal: 小型微型计算机系统

Included Journals: CSCD、ISTIC、PKU

Volume: 27

Issue: 9

Page Number: 1726-1730

ISSN: 1000-1220

Key Words: 最大流;增载轨算法;预流推进算法;实验性能

Abstract: 通过放松Ahujia和Orlin算法的约束, 给出了一个新的增载轨算法. 该算法实质上提供了一个构造、阻塞无环网络的策略, 它可以在每次构造无环网络中得到更多的增载轨, 从而进一步降低了找到每条增载轨的代价. 实验表明, 新的算法比Dinic算法快2～5倍, 和目前实验性能最好的预流推进算法基本相近. 说明增载轨类算法在实际性能方面未必落后于预流推进类算法.