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

计算机科学 ›› 2005, Vol. 32 ›› Issue (10): 38-40.

• 计算机网络与信息安全 • 上一篇下一篇

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

徐周波古天龙赵岭忠

桂林电子工业学院计算机系,桂林541004

出版日期:2018-11-17 发布日期:2018-11-17
基金资助:
本文工作得到国家自然科学基金（60243002）、教育部留学归国人员基金及广西自然科学基金（0448072）的资助.

XU Zhou-Bo ,GU Tian-Long ,ZHAO Ling-Zhong（School of Computer Science, Guilin University of Electronic Technology, Guilin 541004）

Online:2018-11-17 Published:2018-11-17

摘要/Abstract

摘要： 本文通过对网络及网络最大流问题的符号代数判定图（ADD）描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法.与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善.实验结果表明,本文算法是切实有效的,且可处理更大规模的问题.

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

Abstract: 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 Hach

Key words: Symbolic algorithms, Maximum flow, Algebraic decision diagram （ADD）, Residual network

徐周波古天龙赵岭忠. 网络最大流问题求解的符号ADD增广路径算法[J]. 计算机科学, 2005, 32(10): 38-40. https://doi.org/

XU Zhou-Bo ,GU Tian-Long ,ZHAO Ling-Zhong（School of Computer Science, Guilin University of Electronic Technology, Guilin 541004）. [J]. Computer Science, 2005, 32(10): 38-40. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0