广义最大并行流算法的改进

• 作者: 唐恒永 董丽薇 赵大宇
• 来源期刊: 系统管理学报
• 学科: 数学
• 关键词: 广义最大并行流 全多项式时间近似算法 算法复杂性 lossy网络 获得因子 广义的最短路
• 年，卷（期）: 2007,（6）
• 所属期刊栏目: 学术论文
• 页码范围: 678-684
• 页数: 7页
• 分类号: O221.7|O157.5
• 字数: 6229字
• 语种: 中文
• DOI: 10.3969/j.issn.1005-2542.2007.06.017

摘要

研究了Karakostas G给出的求解最大并行流问题的一个近似算法,将其算法的参数进行了改进,给出了算法的时间复杂性不依赖于物资数k的广义最大并行流的全多项式时间近似算法,该算法只适用于广义的lossy网络.用改进后算法求出的目标函数值更接近于最优值,对该近似算法的近似性和算法的时间复杂性进行了证明.最后,用C语言编程,计算数值例子,通过对比充分验证了改进后算法的正确性和有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐恒永		75	433	11.0	16.0
2	赵大宇		17	143	7.0	11.0
3	董丽薇		14	31	2.0	5.0