网络最大流问题求解的符号ADD增广路径算法  

An Augmenting-Path-Based Symbolic ADD Algorithm for Maximum Flow in Networks

作　　者：徐周波[1] 古天龙[1] 赵岭忠[1] 

机构地区：[1]桂林电子工业学院计算机系,桂林541004

出　　处：《计算机科学》2005年第10期38-40,54,共4页Computer Science

基　　金：国家自然科学基金(60243002);教育部留学归国人员基金;广西自然科学基金(0448072)

摘　　要：本文通过对网络及网络最大流问题的符号代数判定图(ADD)描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法。与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善。实验结果表明,本文算法是切实有效的,且可处理更大规模的问题。In this paper, the augmenting-path-based symbolic ADD （Algebraic Decision Diagram） algorithm for maximum flow in networks is proposed. In the algorithm, the network and the maximum flow problem are formulated via ADD （Algebraic Decision Diagram）, and Hachtels＇ symbolic algorithm for maximum flow in unit capacity networks is integrated with Gabow＇ s scaling algorithm to transfer the general problem into a sequence of maximum flow problem in unit capacity network. The simulation results show that the novel symbolic algorithm can improve the space complexity, compared with Dinic＇s algorithm and Karzanov＇s algorithm, and can be used to handle larger-scale general network flow problems.

关 键 词：符号算法 最大流 代数判定图(ADD) 剩余网络 网络最大流 路径算法 问题求解 ADD 符号 最大流问题 变尺度算法 空间复杂度 求解算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] O157.5[自动化与计算机技术—计算机科学与技术]