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

• 作者: 古天龙 徐周波
• 来源期刊: 桂林电子工业学院学报
• 学科: 工学
• 关键词: 符号算法 最大流 代数决策图(ADD)
• 年，卷（期）: 2004,（3）
• 所属期刊栏目: 学术论文
• 页码范围: 54-57
• 页数: 4页
• 分类号: TP301.6
• 字数: 3522字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-808X.2004.03.012

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	古天龙	桂林电子工业学院学院办公室	207	1546	18.0	30.0
2	徐周波	桂林电子工业学院计算机系	53	284	8.0	15.0