网络最短路的提速问题

• 作者: 叶希琼 张振坤
• 来源期刊: 河南科学
• 关键词: 网络最短路 线性规划 网络提速 算法
• 年，卷（期）: 2012,（3）
• 所属期刊栏目: 数学研究与应用
• 页码范围: 302-307
• 分类号: O157.6|O22
• 语种: 中文
• DOI: 10.3969/j.issn.1004-3918.2012.03.011

摘要

网络最短路提速问题起源于交通运输、计算机信息传输等领域,具有重要的理论和实际应用意义.对一般网络来说,该问题是NP-完全的.对(0,1)-提速问题的指定路线的提速问题两种情况分别进行了研究,证明了(0,1)-提速问题是NP-完全的、一般网络在指定路线情形下的提速问题是多项式可解的,给出了单源多汇网络G中提速问题的O(nm log n)算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张振坤	黄淮学院数学系	22	22	3.0	3.0
2	叶希琼	郑州电子信息工程学校公共教学部	1	2	1.0	1.0