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

摘要：

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

关键词：符号算法、最大流、代数判定图(ADD)、剩余网络

所属期刊栏目：32

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金;教育部留学回国人员科研启动基金

在线出版日期：2005-11-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：38-40,54