%0 Journal Article
%T An Augmenting-Path-Based Symbolic ADD Algorithm for Maximum Flow in Networks<br>网络最大流问题求解的符号ADD增广路径算法
%A XU Zhou-Bo
%A GU Tian-Long
%A ZHAO Ling-Zhong
%A <br>徐周波
%A 古天龙
%A 赵岭忠
%J 计算机科学
%D 2005
%I 
%X In this paper, the augmenting-path-based symbolic ADD (Algebraic Decision Diagram) algorithm for maxi- mum 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 complexi- ty, compared with Dinic's algorithm and Karzanov's algorithm, and can be used to handle larger-scale general network flow problems.
%K Symbolic algorithms
%K Maximum flow
%K Algebraic decision diagram (ADD)
%K Residual network<br>符号算法
%K 最大流
%K 代数判定图（ADD）
%K 剩余网络
%K 网络最大流
%K 路径算法
%K 问题求解
%K ADD
%K 符号
%K 最大流问题
%K 变尺度算法
%K 空间复杂度
%K 求解算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=D5A8F394706DF400&yid=2DD7160C83D0ACED&vid=9971A5E270697F23&iid=F3090AE9B60B7ED1&sid=16D8618C6164A3ED&eid=1371F55DA51B6E64&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=9