DoubleTree:A New Efficient Maximum-Flow Algorithm

摘要：

This paper presents a new maximum-flow algorithmDoubleTree algorithm,which proposes a new augment way,i.e. alternant augment from the source and the sink in an effort to form the source augment tree and the sink augment tree. A path from the source to the sink will be found once the two trees meet. In this paper,the DoubleTree algorithm,and DINIC,ISAP and HLPP algorithms are analyzed and compared. As shown by the test,the DoubleTree algorithm is more efficient than the above-mentioned three algorithms in sparse graph,dense graph and bipartite graph.

关键词： network flow algorithm maximum-flow algorithm DoubleTree algorithm

作者: Zijie Li Zhen Zhang

作者单位: Department of computer science,Jinan University,Guangzhou,China

会议类型: 国际会议

会议名称: 2011 International Conference on Opto-Electronics Engineering and Information Science(2011光电电子工程与信息科学国际会议 ICOEIS 2011)

会议地点: 西安

会议语种:英文

页码: 17-21

在线出版日期: 2011-12-23（万方平台首次上网日期，不代表论文的发表时间）