网络最大流问题的一种新的符号ADD求解算法  

A novel symbolic ADD algorithm for maximum flow in networks

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

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

出　　处：《通信学报》2005年第2期1-8,共8页Journal on Communications

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

摘　　要：通过对网络及网络最大流问题的符号代数判定图描述,在Trff算法的基础上,给出了网络最大流问题的一种新的符号ADD求解算法。与Dinic、Karzanov算法相比,本文算法的空间复杂度较低。实验结果表明,该算法可处理更大规模的问题。The maximum flow problem was formulated by ADD (algebraic decision diagram). Based on Trffs algorithm, a novel symbolic algorithm for the maximum flow problem was then proposed. The simulation results show that the symbolic algorithm can reduce the space complexity much, compared with Dinics algorithm and Karzanovs algorithm, and can be used to handle larger-scale network flow problems.

关 键 词：网络优化 最大流 符号算法 代数判定图 

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