| 星图上最短路改进问题的组合算法 |
| |
| 引用本文： | 台伟英,湛宁,王勤.星图上最短路改进问题的组合算法[J].中国计量学院学报,2011,22(4):394-397. |
| |
| 作者姓名： | 台伟英 湛宁 王勤 |
| |
| 作者单位： | 1. 中国计量学院理学院,浙江杭州,310018
2. 信阳职业技术学院数学与计算机科学学院,河南信阳,464000 |
| |
| 基金项目： | 国家自然科学基金资助项目，浙江省自然科学基金项目资助 |
| |
| 摘 要： | 给定星图中一个非中心点到其余所有非中心点之间的n对点对,当要求网络中边的权重只允许减少且减少量有上界,并且这n对点对的最短路长度都不超过给定的n个上界的条件下,研究了l1模下星图的最短路改进问题,得到了解该问题的强多项式时间的组合算法,算法的时间复杂度为O(|E|log|E|).
|
| 关 键 词： | 最短路改进问题 l1模 组合算法 强多项式时间算法 |
The combinatorial algorithm for shortest path improvement problem on star graph |
| |
| TAI Wei-ying,ZHAN Ning,WANG Qin.The combinatorial algorithm for shortest path improvement problem on star graph[J].Journal of China Jiliang University,2011,22(4):394-397. |
| |
| Authors: | TAI Wei-ying ZHAN Ning WANG Qin |
| |
| Affiliation: | TAI Wei-ying1,ZHAN Ning2,WANG Qin1(1.College of Sciences,China Jiliang University,Hangzhou 310018,China,2.Mathematics and Computer Science Department,Xinyang Vocational and Technical College,Xinyang Henan 464000,China) |
| |
| Abstract: | Given n vertex pairs from a non-center vertex to all other non-center vertices in a star graph,we considered the shortest path improvement problem under l1 norm,where the edge weights could only be decreased with the given intervals and the lengths of the shortest paths of the given vertex pairs must satisfy the given bounds.We give a combinatorial algorithm to solve the problem at strongly polynomial time,which runs in O(|E|log|E|) time. |
| |
| Keywords: | shortest path improvement problem l1 norm combinatorial algorithm strongly polynomial time algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
