最大一致流问题的一个逼近算法

• 作者: 吴亚坤 程丛电 郭海旭
• 来源期刊: 辽宁大学学报（自然科学版）
• 学科: 数学
• 关键词: 多物资网络流 逼近 算法 复杂性
• 年，卷（期）: 2009,（1）
• 页码范围: 35-39
• 页数: 5页
• 分类号: O157|O221
• 字数: 2596字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-5846.2009.01.010

摘要

通过建构辅助网络,以Korte和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索, 给出了一个新的求解最大一致流问题的逼近算法. 然后,进行算法分析,说明了所建立的算法是拟多项式算法,并且给出与证明了一个有关输出的流与输入问题的解之间的逼近关系.该项工作表明从一个多种物资网络流问题的算法出发通过变换求解其他有关问题是可行的,并且为研究网络流问题提供了一种新的方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	程丛电	沈阳师范大学数学与系统科学学院	32	61	5.0	7.0
2	吴亚坤	辽宁大学计算中心	17	128	7.0	11.0
3	郭海旭	辽宁大学计算中心	4	22	2.0	4.0