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

The combinatorial algorithm for shortest path improvement problem on star graph

给定星图中一个非中心点到其余所有非中心点之间的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.