网络最大流问题求解的代数决策图(ADD)技术

摘要：

Hachtel G.D.和Somenzi F.提出的0-1网络最大流问题的符号有序二叉决策图(OBDD)算法在一定程度上缓减了"状态爆炸"问题,但算法仅局限于求解0-1网络的最大流.Bachar R.I.等提出的代数决策图(ADD)数据结构,是描述伪布尔函数和有限域取值函数的一种有效技术.文中利用ADD存储表示网络及描述网络最大流问题,给出一种求解网络最大流问题的符号ADD技术新思路.实验结果说明了应用ADD技术求解一般网络最大流问题的有效性,可处理0-1网络最大流问题的符号OBDD算法无法处理的非0-1网络.

关键词：符号算法、最大流、代数决策图(ADD)

所属期刊栏目：24

分类号：TP301.6(计算技术、计算机技术)

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

页数：共4页

页码：54-57