星图上最短路改进问题的组合算法

• 作者: 台伟英 湛宁 王勤
• 来源期刊: 中国计量学院学报
• 学科: 工学
• 关键词: 最短路改进问题 l1模 组合算法 强多项式时间算法
• 年，卷（期）: 2011,（4）
• 页码范围: 394-397
• 分类号: TP301|O221
• 字数: 3433字
• 语种: 中文
• DOI: 10.3969/j.issn.1004-1540.2011.04.019

摘要

给定星图中一个非中心点到其余所有非中心点之间的n对点对,当要求网络中边的权重只允许减少且减少量有上界,并且这n对点对的最短路长度都不超过给定的n个上界的条件下,研究了l1模下星图的最短路改进问题,得到了解该问题的强多项式时间的组合算法,算法的时间复杂度为O(| E |log | E |).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王勤	中国计量学院理学院	27	138	5.0	10.0
2	湛宁	信阳职业技术学院数学与计算机科学学院	19	103	5.0	10.0
3	台伟英	中国计量学院理学院	1	0	0.0	0.0