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

The combinatorial algorithm for shortest path improvement problem on star graph

作　　者：台伟英[1] 湛宁[2] 王勤[1] 

机构地区：[1]中国计量学院理学院,浙江杭州310018 [2]信阳职业技术学院数学与计算机科学学院,河南信阳464000

出　　处：《中国计量学院学报》2011年第4期394-397,共4页Journal of China Jiliang University

基　　金：国家自然科学基金资助项目(No.11171316);浙江省自然科学基金项目资助(No.Y6090472)

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

关 键 词：最短路改进问题 l1模 组合算法 强多项式时间算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O221[自动化与计算机技术—计算机科学与技术]